# What is the complexity of these various algorithms?

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++;
}
``````

###### Who is Participating?

Commented:
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

Commented:
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

Commented:
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 Commented:
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 Commented:
I want to say Big Theta(n) for #4
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.