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

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?

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.

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