Solved

# What is the complexity of these various algorithms?

Posted on 2011-05-04
402 Views
What is the complexity of these various algorithms?

#1
``````for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
x++;
}
}
``````

#2
``````for(int i=0; i<n; i++){
for(int j=0; j<i; j++){
x++;
}
}
``````

#3
``````for(int i=n; i>0; i--){
for(int j=0; j<n; j++){
x++;
}
}
``````

#4
``````for(int i=n; i>0; i--){
for(int j=0; j<i; j++){
x++;
}
}
``````

#5
``````for(int i=n; i>0; i/2){
for(int j=n; j>0; j/2){
x++;
}
}
``````

#6
``````for(int i=n; i>0; i/2){
for(int j=i; j>0; j/2){
x++;
}
}
``````

#7
``````for(int i=n; i>0; i/2){
x++;
}
``````

0
Question by:Eindoofus

LVL 37

Expert Comment

How about you make some guesses and I'll tell you if you're right (and I'll also explain all the answers then).
0

LVL 37

Expert Comment

Hint1: 1+2+3+4+5+...+n = (n^2 + n)/2 = O(n^2)
Hint2: n + n/2 + n/4 + n/8 + ... + 1 = 2n = O(n)

That should get you all of them.
0

Author Comment

I made these different variations up in preperation for my midterm. I'm guessing they are 1.) Big Theta(n^2), 2.) Big Theta(n) 3.) Big Theta(n lg n), 4.) not sure, 5.) Big Theta(lg n), 6.) Big Theta(lg n), 7.) Big Theta(lg n)

Is that correct? And what would #4 be?
0

Author Comment

I want to say Big Theta(n) for #4
0

LVL 37

Accepted Solution

I'll use T() for big theta

Remember, you are basically just counting the number of times the x++ gets called.

1. Yes: Simple. Easy. T(n^2)

2. No: Note that the x++ line runs once the first time, then twice the second, etc. so it's 1+2+3+...+n which is T(n^2)

3. No: Double for loop again. Simple T(n^2) I think you just misread maybe here

4. No: This is 1+2+3+...+n again. T(n^2)

5. Yes: lg(n)*lg(n) = lg(2n) = T(lg(n))

6. Yes: lg(n) + lg(n/2) + lg(n/4) = T(lg(n))

7. Yes: Simple T(lg(n))
0

## Featured Post

### Suggested Solutions

sum13 challenge 24 68
Line meaning 9 56
Python 2.7 - French characters 6 29
SQL400 max size 5 33
Software development teams often use in-memory caches to improve performance. They want to speed up access to, or reduce load on, a backing store (database, file system, etc.) by keeping some or all of the data in memory.   You should implement a …
"Disruption" is the most feared word for C-level executives these days. They agonize over their industry being disturbed by another player - most likely by startups.
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.