CODEWITHSUNDEEP
time-complexity
nightowl_nicky
nightowl_nicky

Reputation: 361

Time complexitiy: Which is slower? (O(N^3) or O(2^N))

I'm learning time complexity recently and just wondering which Big-O Complexity is slower O(N^3) or O(2^N)? And why would you say that? I can find a lot of information compared to O(N^2), O(2^N) but not O(N^3). Thank you.

Upvotes: 0

Views: 78

Answers (2)

Gopherkhan
Gopherkhan

Reputation: 4342

Big-O is about measuring the scalability of an algorithm. Basically, as the number of inputs grow, what will the performance characteristics be like? Can you expect your algorithm's runtime to grow linearly (e.g. will 3x as many inputs will take only 3x as long), or will your application grind to a halt under the load?

With that in mind, just try plugging in some large numbers. 

100,000 ^ 3 = 1e+15
2 ^ 100,000 = Infinity (read: too big for google's calculator)

Clearly the N in the exponent is far more expensive.

Upvotes: 1

huseyin tugrul buyukisik
huseyin tugrul buyukisik

Reputation: 11916

Changes to the "power" has greater effect than changing the "base", unless base is close to one (floating point 1.00001f).

So slowness is wildly increasing when N>2 because of N being power in the O(2^N)

Upvotes: 0

Related Questions