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

Open in new window


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

Open in new window


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

Open in new window


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

Open in new window


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

Open in new window


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

Open in new window


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

Open in new window


EindoofusAsked:
Who is Participating?
 
TommySzalapskiConnect With a Mentor 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
 
TommySzalapskiCommented:
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
 
TommySzalapskiCommented:
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
 
EindoofusAuthor 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
 
EindoofusAuthor 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.

All Courses

From novice to tech pro — start learning today.