CODEWITHSUNDEEP
time-complexitybig-o
Nithux
Nithux

Reputation: 35

Big O-Notation complexity order

I have read about the Big-O complexity order. On the internet it said the order is:

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O (2^n) < O (10^n)

Now I want to sort these O-Notations in their complexity order going from the lowest to the highest.

a: O(π^e n^2)   
b: O(n+n^2/√n^3)  
c: O((1/10^100)n!+5n^2)  
d: O(25√9n)  
e: O(log(n^n)

Is the order e, d, a, b correct? I am not sure where c belongs.

Upvotes: 1

Views: 940

Answers (1)

Dici
Dici

Reputation: 25950

First, note that mathematically speaking, I've never heard about a properly defined order relationship on the image of the O operator, so when you're saying O(1) < O(log n), as far as I know there is no mathematical definition for it and it only means that an algorithm performing with a complexity of O(1) will be slower (for large problems) than an algorithm with a complexity of O(n).

Now to answer your question, let's simplify all expressions:

a: O(π^e n^2)           <=> O(n^2)      (a constant factor doesn't affect the nature of complexity itself although it will impact running time)
b: O(n+n^2/√n^3)        <=> O(n^2/√n^3) (eliminating a term that evolves slower than the other term) 
                        <=> O(√n)       (simplifying expression)
c: O((1/10^100)n!+5n^2) <=> O(n!)       (eliminating a term that evolves slower than the other term and removing constant factors)
d: O(25√9n)             <=> O(n)        (removing constant factors)
e: O(log(n^n))          <=> O(n log(n)) (simplifying expression)

Now it becomes clear that the "order", from faster to slower, will be: b, d, e, a, c

Upvotes: 1

Related Questions