Solved

Posted on 2011-05-04

What is the complexity of these various algorithms?

#1

#2

#3

#4

#5

#6

#7

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

5 Comments

Hint2: n + n/2 + n/4 + n/8 + ... + 1 = 2n = O(n)

That should get you all of them.

Is that correct? And what would #4 be?

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))

Title | # Comments | Views | Activity |
---|---|---|---|

sum13 challenge | 24 | 68 | |

Line meaning | 9 | 56 | |

Python 2.7 - French characters | 6 | 29 | |

SQL400 max size | 5 | 33 |

This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**16** Experts available now in Live!