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

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
   }
}

Open in new window

But what is the complexity of this?:
int i=n;
while(i>0) {
   for(int k=1; k<n; k++){
      x++;
   }
    i=i/2
}

Open in new window

0
Eindoofus
Asked:
Eindoofus
  • 3
1 Solution
 
TommySzalapskiCommented:
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
 
TommySzalapskiCommented:
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
 
TommySzalapskiCommented:
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

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

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