[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 423
  • Last Modified:

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


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

Vote for the Most Valuable Expert

It’s time to recognize experts that go above and beyond with helpful solutions and engagement on site. Choose from the top experts in the Hall of Fame or on the right rail of your favorite topic page. Look for the blue “Nominate” button on their profile to vote.

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