educative.io

Nested For-loop with dependent variables#

Courses
,
#1

I am trying to see the difference of how we are solving this example (nested for loop with dependent) vs Big O of a Nested Loop with Addition.
In the dependent example we say that the statement in the inner loop running time is cn(n−1)/2 but in almost all the following challenges and in the example of the addition challenge we say the statement in the inner loop runs (n/3 * n/2) steps. In the challenges we often calculate the steps by multiplying the steps of the outer loop * steps of inner loop.
In the dependent example we use cn(n−1)/2 instead of saying that the outer loop runs n times and the statement in the inner loop as well so we can do n * n steps.
Why do we not use the n(n−1)/2 in the Nested Loop with Addition challenge or other challenges as well ?
​

​

Course: https://www.educative.io/courses/big-o-notation
Lesson: Educative: Interactive Courses for Software Developers

#2

Hi @Georges_Chami,
Thanks for reaching us!

These are two different scenarios for calculating the time complexity.

  1. In the “Nested For-loop with dependent variables”, the execution of the inner loop depends on the outer loop value. The inner loop iterates from 0 to the loop variable i of the outer loop. As soon as the iteration of the outer loop increases, the total iteration of the inner loop increases.
  2. Meanwhile, in the Nested loop with addition challenge, the execution inner loop isn’t dependent on the outer loop. The inner loop has a fixed number of iterations in each iteration of the outer loop.

If you are trying to map the challenges scenarios with the common complexity scenarios, you can map it with the “For-loop with increments of size k”, where the time complexity becomes n/k. If inner and outer loops are independent, we can simply multiply the time complexity of both loops.

I hope you got the difference. If there is any confusion left, do let us know.
Thanks and Happy Learning!