The outer loop is logn and the inner loop runs n + n/2+n/4+…1 so it is 2n-1

logn * (2n-1) = logn * n

so complexity is O(nlogn)

The outer loop is logn and the inner loop runs n + n/2+n/4+…1 so it is 2n-1

logn * (2n-1) = logn * n

so complexity is O(nlogn)

Try to think just how many times the instruction “count += 1” is executed.

You can also try to code it and execute it to convince you.

The increment, that at the end should reflect the time complexity, will be executed just:

N + N/2 + N/4 + … + N/(N-1) + 1

exactly like you wrote. You don’t have to multiply for the log(N) of the external loop because the two loop are interdependent.

So the final complexity is just the number of executions of the increment, which is: O(2N) => O(N)

so basically if we have nested loops and the inner element is dependent on outer element then tc of outer loop does not matter… is that correct??