• Status: Solved
• Priority: Medium
• Security: Public
• Views: 414

# What is the complexity of this algorithm?

I was told something like the following code is Big Theta(n lg n):
``````int i;
for(int k=1; k<n; k++){
i=n;
while(i>0) {
x++;
i=i/2
}
}
``````
But what is the complexity of this?:
``````int i=n;
while(i>0) {
for(int k=1; k<n; k++){
x++;
}
i=i/2
}
``````
0
Eindoofus
• 3
1 Solution

Commented:
The first one is n*lgn because the for loop runs n times and the while loop runs lgn times (since it's cut in half every time)

The second one is the same thing only flipped. So it runs in lgn*n which is the same thing.

1: For each of n items do lgn things = n*lgn
2: For each of lgn items do n things = lgn*n = n*lgn
0

Commented:
I'm sorry, that's incorrect. In the second one the first loop runs n times, then n/2 times, then n/4 times, then n/8 times, etc.
So it's n+n/2+n/4+... = 2n so it's O(2n) which is the same as O(n)
0

Commented:
Ignore my second post. If the second one was
k<i then it would be O(2n)=O(n), but since it's k<n, then my first post applies.
0

## Featured Post

• 3
Tackle projects and never again get stuck behind a technical roadblock.