Big-O Nested While Loop
big-o, complexity-theory, time-complexity
Solution
You may proceed formally, step by step, using Sigma notation to obtain the exact number of iterations - Look at Discrete Loops and Worst Case Performance paper (page 10).
The result has been empirically verified.
Problem
``` i <-- 1 while(i < n) j <--1 while(j < i) j <-- j * 2 i <-- i + 1 done ``` My shot at this would be `O(log n)` for the inner loop. And I'm guessing the outer loop is `O(n)`, for an overall complexity of `O(n log n)`. Confirm?