CODEWITHSUNDEEP
algorithmmethodssubstitutionnotation
user1817347
user1817347

Reputation: 45

Asymptotic notation from running time

If I have an algorithm with the running time T(n) = 5n^4/100000 + n^3/100, I know that I get Θ(n^4).

Now, if I have something like T(n) = (10n^2 + 20n^4 + 100n^3)/(n^4), does this yield Θ(n^3)?

I am trying to eliminate low-order terms to use the Substitution method to prove this.

Upvotes: 1

Views: 52

Answers (1)

Alma Do
Alma Do

Reputation: 37365

Big-Theta means, that growth is both big-O and big-Omega.

So first case in your question is Θ(n^4), not Θ(n^3) since 5n^4/100000 + n^3/100 belongs to O(n^4) and not O(n^3).

Second case:

enter image description here

Thus, it's Θ(1) - because result is O(1) and Ω(1): all members, except 20 (constant) will limit to zero when n is growing.

Upvotes: 3

Related Questions