Give the worst case time complexity of the following function. Justify your answer.
i = 1;while (i < n) { j = 2; while (j < n) j = j * j; i++;}
Difficulty level
This exercise is mostly suitable for students
We observe that the outer loop (on counter j ) just increments one by one. So, that loop runs in O(n) time.
The inner loop runs on counter k , and the value of k gets squared every time, starting with 2 .
Therefore, the value of k jumps from 2 , to 4 , to 16 to 256 . We observe that after m iterations of the loop, the value of k becomes 2 2^m . The loop terminates when the value of k becomes larger or equal to n , that is, 2 2^m ≥ n , that is, m ≥ log log (n) . Therefore the inner loop runs in O(log log n) time .
Since the two loops are nested, the entire program runs in O(n log log n) time.Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Width of binary trees - recursive version