What is the complexity of the following loop?
Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.Sign up to join this community
Despite the apparent simplicity of the question, I think it is quite tricky.
...I'll go as far as to say it cannot be expressed in "big O" notation ...or at least not in the usual sense with logs and exponentials.
Let me explain. In terms of "big O" notation, you should be able to know how many steps are required in terms of
n. To do that, you need to know when your
Let me rename it into
f for the sake of usual math notation, and
j the number of iterations. This boils down to solving the recursive formula:
f(j) = 2^f(j-1)
...which has no solution that can be expressed in terms of "elementary functions" of
j (the number of steps) according to:
It would be a big O using following this notation:
this is an iteration so we have to unfold the loop say i is taking value 1 to 2^k in the pattern 1,2,4,8,16....2^k i.e. 2^0,2^1,2^2,2^3 this way where sum is being executed k times upto 2^k equals n 2^k=n k=logn and it is O(log n) and also the best worst case is same so the ans will be Theta(logn)