Solved

# What is the complexity of this algorithm?

Posted on 2011-05-04
397 Views
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
Question by:Eindoofus

LVL 37

Accepted Solution

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

LVL 37

Expert Comment

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

LVL 37

Expert Comment

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

### Suggested Solutions

Decrease number proportionately 20 75
has22 challenge 11 56
modThree challenge 4 51
groovy example issue 10 32
The Fluent Interface Design Pattern You can use the Fluent Interface (http://en.wikipedia.org/wiki/Fluent_interface) design pattern to make your PHP code easier to read and maintain.  "Fluent Interface" is an object-oriented design pattern that r…
Introduction This article explores the design of a cache system that can improve the performance of a web site or web application.  The assumption is that the web site has many more “read” operations than “write” operations (this is commonly the ca…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…