For the given code, What is the time complexity in Big - O notation?
for(i = 1; i <= n; i *= 2)
for(j = 0; j <= i; j++)
some_constant_statement
First loop takes logn time but what about second loop ?. I'm confuse please help me to understand this.
The outer loop is O(log n) as it runs a number of times proportional to log(some number n).
The inner loop (taken only by itself) is O(n) as it runs a number of times proportional to some number n. This is true for every iteration of the outer loop, because the time complexity remains the same, i.e. It is always proportional to the value of n at the time it was invoked.
The entire piece of code is O(n log(n)). Usually taken to mean "on the order of some number n multiplied by log(n)".
Big O notation is intended to classify, not quantify. It gives some idea of how the function being discussed will perform with data sets of varying sizes. Two functions described as having O(n log(n)) performance may vary substantially for given values of n.
O(n.log(n))
O(n). What are you actually asking about? The complexity of the inner code or the entire piece of code?O(n.log(n)), but it varies. When n is 16, the inner loop runs 31 times. When n is 15 the inner loop runs 15 times.The time complexity would be O(nlog(n)), but it is an asymptotic complexity. If you want the actual count of the times it would run it would be a bit less than the upper bound. What you can do to visualize this is trace down the whole thing for small values of N.
In this case, say if N = 8
i = 1: j = 0 => 2 times
j = 1
i = 2: j = 0 => 3 times
j = 1
j = 2
i = 4: j = 0 => 5 times
j = 1
j = 2
j = 3
j = 4
i = 8: j = [0,8] => 9 times
and so on for larger values of N...
So it is not increasing linearly but in some sort of exponential fashion and on plotting a graph for larger values and finding upper bound function you would prove that it has an upper bound of O(nlog(n)) if you are mathematically inclined to prove it.
