educative.io

Educative

Runtime of nested loop with index modification

In the explantation, it was derived that a nested loop with index modification (e.g., outer loop increments the i value by i*2) may have up to O(n) complexity. When I tried executing the code, the total runtime count of outer + inner loop is definitely more than O(n).

Outer loop ~ log(n)
Inner loop ~ (log (n) ) . n

To me, it almost looks like this algorithm is having O(nlog(n)) complexity. Please correct me if I’m wrong.

Hi @Kathir

The time complexity of the inner loop is not O(nlog(n)). It would have been O(nlog(n)) if the inner loop was running n times, but it’s running unto i. Therefore, with reference to the calculations given in the table in the lesson, the time complexity turns out to be O(n).

Secondly, to answer your question “When I tried executing the code, the total runtime count of outer + inner loop is definitely more than O(n).”, I hope you aren’t confusing the exact number of steps with the time complexity because time complexity is given in terms of Big-O which represents an upper bound. Therefore, it’s possible that you have N=10 but your O(n) algorithm runs 13 steps.