CODEWITHSUNDEEP
while-loopbig-otime-complexity
Sean
Sean

Reputation: 1313

Big O - Time Complexity puzzling for while loops

As a time complexity example (refreshing my mind) I am attempting to solve find the running time (in terms on n) of the following algorithm:

for (i=1; i <= n; i++) {      //O(n)
  k = 1;
  for (j=1; j <= i; j++) {    //O(n)
    k = 2*k;
  }
  j = k*k;
  while (j > 1) {             //O(..?)
    j = j / 2;
  }
}

I understand the first two for loops combined take O(n^2), however I am a little perplexed at how to find the running time of a while loop. Although I know the while loop runs twice the first execution, then 4 times, then 6... all multiples of 2. Would that just make it run O(nlog(n)) times?

Upvotes: 0

Views: 289

Answers (2)

A.S.H
A.S.H

Reputation: 29332

For each value of i, we execute two loops.

The first one executes i times for each value of i The third one, j start at 2^i and is divided successfully by 2, so it also executes i times.

in total, we have O(1+2+..+n) ~ O(n(n+1)/2) ~ O(n^2)

Upvotes: 0

Mr. Llama
Mr. Llama

Reputation: 20889

The repeated division is log_2(j) which is the same as log(j) / log(2). The log(2) is constant, so it's just written as log(j).

Because the O(log(n)) is at the same depth as the O(n) loop and the O(n) loop dwarfs the O(log(n)) loop, the two combined takes O(n) time.

The final time complexity will be O(n^2).

Upvotes: 1

Related Questions