Bill
Bill

Reputation: 21

Big O Notation Confusion

Ordering from smallest to largest and wondering where I have made errors? Equivalents are on the same line. I'm really confused about where O(sqrt(n)) would fall on the list?

1. O(log n)
2. O(n)
3. O(2^2 n)
4. O(2n log n)
5. O(n log n)
6. O(n log n^2)
7. O(sqrt(n))
8. O(n^1.5) 
9. O(n^2)   O(2n^2)  O(n^2 log n)
10. O(n^3)
11. O(k^2) O(2^n)

Upvotes: 0

Views: 69

Answers (2)

sam46
sam46

Reputation: 1271

O( ) omitted for convenience:

k^2 (assuming k is constant??)  
log n 
sqrt n == n^0.5   
n == (2^2) n   
n log n == 2n log n == n log(n^2)   
n^1.5  
n^2 == 2n^2  
n^2 log n  
n^3  
2^n  

Upvotes: -1

taurus05
taurus05

Reputation: 2546

This might help you, in better understanding the order of complexites.

enter image description here

Upvotes: 2

Related Questions