CODEWITHSUNDEEP
algorithmwhile-loopbig-o
user3818430
user3818430

Reputation: 119

Determining Big-o While Loop

// n > 0 

i ← 0 
while (i < n) 
     j ← 0 
     while (j < power(2,i)) 
         j ← j + 1 
     done 
    i ← i + 1 
done

Is the overall complexity O(n(log(n)) because the inner while loop has a conditional where 2^i so 2^0 2^1 2^2 ... = 1 2 8 16 32 64 128... etc. So for 2^i < n --> log(n) > i?

And the outer loop looks to be simply O(n).

Multiple both loop complexities for O(n(log(n)), confirm please? Thanks in advance.

Upvotes: 1

Views: 1707

Answers (4)

Khaled.K
Khaled.K

Reputation: 5940

i ← 0 
while (i < n) 
    j ← 0 
    while (j < power(2,i)) 
         j ← j + 1 
    done 
    i ← i + 1 
done

Time Complexity

Time = 2^0 + (2^0 + 2^1) + .. + (2^0 + .. + 2^(n-1))

Time = n * 2^0 + (n-1) * 2^1 + .. + (n-(n-1)) * 2^(n-1)

Time = SUM { (n-k) * 2^k | k = 0..(n-1) }

Time = 2^(n+1) - n - 2

Time ~ O(2^(n+1))

Upvotes: 0

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

Using a formal methodology through Sigma notation:

enter image description here

Upvotes: 3

McLovin
McLovin

Reputation: 3674

It's O(2^n)

For the outer loop, the number of iterations is n, so the inner loop executes for every value of i from 0 to n-1.
The number of iterations of the inner loop each time is 2^i, so the total number of iterations for the entire program is:

2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + ... +2^(n-1)

This sum is equal to 2^n - 1. Because 2^n is so large compared to 1, we can drop the 1 in the big-O notation, giving us O(2^n).

Upvotes: 5

Kevin L
Kevin L

Reputation: 1066

looks like O(2^n), inner loop is a sum of (2^i) from i=0 to i=n-1, which sums to 2^(i)-1 operations

Upvotes: 0

Related Questions