The second one is the same thing only flipped. So it runs in lgn*n which is the same thing.

1: For each of n items do lgn things = n*lgn

2: For each of lgn items do n things = lgn*n = n*lgn

Solved

Posted on 2011-05-04

I was told something like the following code is Big Theta(n lg n):

```
int i;
for(int k=1; k<n; k++){
i=n;
while(i>0) {
x++;
i=i/2
}
}
```

But what is the complexity of this?:```
int i=n;
while(i>0) {
for(int k=1; k<n; k++){
x++;
}
i=i/2
}
```

3 Comments

The second one is the same thing only flipped. So it runs in lgn*n which is the same thing.

1: For each of n items do lgn things = n*lgn

2: For each of lgn items do n things = lgn*n = n*lgn

By clicking you are agreeing to Experts Exchange's Terms of Use.

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

Decrease number proportionately | 20 | 75 | |

has22 challenge | 11 | 56 | |

modThree challenge | 4 | 51 | |

groovy example issue | 10 | 32 |

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

Connect with top rated Experts

**22** Experts available now in Live!