CODEWITHSUNDEEP
javadata-structurestime-complexitybig-o
H.Das
H.Das

Reputation: 225

Nested for Loop Time Complexity

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.

Upvotes: 1

Views: 106

Answers (2)

Tibrogargan
Tibrogargan

Reputation: 4603

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.

Upvotes: 1

Kushan Mehta
Kushan Mehta

Reputation: 188

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.

Upvotes: 0

Related Questions