CODEWITHSUNDEEP
constantstime-complexitycomplexity-theory
Nick
Nick

Reputation: 47

Time Complexity - Order of Growth

I have just started learning the order of growth and found the below exercise in the text.

We have the below equation,

T(n) = 3n + 32n^3 + 767249999n^2 = O (?)

Usually, we drop the lower order terms and constants and we would get O(n^3). But in this case, the constant 767249999 is too large and that will make the n2 term bigger even with very large values of n. So, this relation results in O(n^2) or O(n^3)? Thanks!

Upvotes: 0

Views: 65

Answers (1)

Islingre
Islingre

Reputation: 2349

It results in O(n^3). This is due to the fact, that for large enough n (no matter if this is "small", "large" or "very large") the term 32n^3 dominates 767249999n^2.

By the definition, you would need any constant c such that cn^2 is never dominated by 32n^3 for this to be in O(n^2). But this is impossible, as for n > c/32 you will find out that 32n^3 = 32n*n^2 > cn^2.

Upvotes: 1

Related Questions