A reader asked us the following question:
The outer loop is O(logn), so the inner loop would be O(n*logn)?
The complexity of this algorithm cannot be O(log(n)) because here inner loop runs var times, not n times. So when we sum the var values for all the iterations of the outer loop we will get:
(2^k2^1)-1
Put 2^k = n Since n>2^k
2n-1
The inner loop will run 2n-1 times in total (Considering all the iterations of the outer loop), and the outer loop will run log(n) times. So the overall complexity will be
2n-1+log(n)
O(n)
When the counter variable of the inner loop is dependent on the value of the outer loop counter variable, we calculate the complexities in a different way. We will calculate the individual complexity of the inner and outer loop and then sum the overall complexity. Keeping this concept in mind, we will calculate the complexities of such algorithms.
2 Likes
Hey Maida_ljiaz,
I share the same thought as coderust. The inner loop is repeated LogN, besides its inside runs of N.
Therefore it should be NLogN times…making the Big O(NLogN) the considered answer.