CODEWITHSUNDEEP
algorithmtime-complexity
DavidB
DavidB

Reputation: 301

Derive Complexity of Algorithm

I'm studying for an exam and have run into this problem:

j=n
while (j>=1) {
  for i=1 to j
    x= x+1;
  j=j/2
}

The question is to derive theta notation for the number of times that x = x+1 is executed. To me this looks likes an nlog(n). Not sure if this is true or not. What techniques are recommended for analyzing this algorithm more mathematically? I mean like a step by step solution.

Any help would be greatly appreciated.

Upvotes: 0

Views: 277

Answers (4)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

Methodically, using Sigma notation:

enter image description here

(Empirically verified).

Upvotes: 2

Jason Baker
Jason Baker

Reputation: 2481

You can analyze the complexity with a recurrence relation:

T(n) = n + T(n/2)

Describes the time complexity of the outer while loop. The first n represents the inner for loop, and the recursive term describes the remaining iterations. If you expand the relation, you get :

T(n) = n + n/2 + n/4 + ... + 1

With some summation tricks, you can find the closed form of this:

T(n) <= 2n - n/(2^(log(n)))

You can prove that 2n grows faster than n/(2^(log(n)) as n grows arbitrarily large, so your algorithm has complexity O(2n) = O(n)

Upvotes: 1

user1935024
user1935024

Reputation:

You can calculate it in this way :

j = n
while(j >= 1){
......
   j /= 2;
}

what is the complexity of it ? 

 j = n, n/2, n/4, n/8, ...., 1   
 j = n/(2^i), .... n/n

when will this loop stop ? when 2^i = n 

n = 2^i , using log => i = log(n)

so it's log(n) but what about the inner loop ?

inner loop executes j times , j = 1, 2, 4, 8, .... , n ( in the example it's n .... 4, 2, 1) 

 so total work = Sum(2^k)[ k = 0, ... , i] where i = log(n)   (geometric series) 
 [2^(log(n)) - 1]/[2 - 1] = (n - 1)/1 = O(n)

Upvotes: 2

marc
marc

Reputation: 6223

For loops that do not exit early, you can just use summations. For this, we want to transform all loops in simple for loops that count up in steps of one. This loop becomes a sum. So

For i = 1 to j
    x = x + 1

Is O(j).

The outer loop then is

j = n
while (j >= 1) {
    something with O(j)
    j = j / 2
}

Observe how we can transform this into

for (i = 0; i <= log2(n); i++) {
    something with O(n * 2^-i);
}

Let's express this again as a sum: O(sum from i = 0 to log2(n) of n * 2^-i).

From math, you might remember that `

sum from i = 0 to k of q^k = (1 - q^(k+1)) / (1 - q)

Lets apply it: O(n * 2 * (1 - 2^(-log2(n)-1))) = O(n * (2 - 1/n)).

As we are looking at big n -> inf: O(2 * n).

Big-O notation disregards constant factors: O(n).

Upvotes: 2

Related Questions