Thanks a ton, regarding the second method (Resolving the loops concurrently) : if we would have the second for loop’s expression3 as ‘j++’ instead of‘j*2’,the complexity would be O(n^2)

Awesome q2a theme

0 votes

Can Someone help me understand the time-complexity of dependent loops?

for example,

Q1>

int i,j;

for(i=1;i<n;i=i++)

{

for(j=1;j<=i;j=j*2) }

Q2>

int i,j; for(i=1;i<=n/2;i=i++) { for(j=1;j<=i;j++) }

+2 votes

Best answer

Whenever there are dependent loops given you can resolve them in two ways:

- Direct way (Eyeballing it)
- Resolve the loops concurrently

**Direct way: **Let’s say we are solving Q1, the inner loop is looping from j = 1 to j = i and it takes multiplicative jumps (j *= 2), so it will take $log_2(i)$ steps, now what’s the maximum value i can take? i can be max n – 1, so complexity of inner loop is O(log(n)) and now take the outer loop as independent, it will have complexity O(n), so total complexity = O(nlog(n))

Similarly for Q2, inner loop will have complexity O(i), i will take maximum value n/2, so complexity of inner loop = O(n), complexity of outer loop is also O(n), so total complexity $O(n^2)$.

**Resolving the loops concurrently: **

Q1

For i = 0, inner loop will run 0 time

For i = 1, inner loop will run 1 time

For i = 2, inner loop will run 2 time

.

.

.

For i = n-1, inner loop will run approximately log(n) times

Total times both loop will run is $$\sum_{k=0}^{n-1}log(k) = log(n!) = O(nlog(n))$$

Q2

For i = 1, inner loop will run 1 time

For i = 2, inner loop will run 2 times

.

.

.

For i = n/2, inner loop will run n/2 times

Total times both loop will run is $$\sum_{k=1}^{\frac{n}{2}}k = \frac{\frac{n}{2}(\frac{n}{2} + 1)}{2} = O(n^2)$$

8,953 questions

3,113 answers

14,322 comments

95,780 users