CODEWITHSUNDEEP
algorithmproof
Dovi Fischman
Dovi Fischman

Reputation: 13

Big-Theta notation

So I am new to all of this and looking for some help and guidance on proving a Big Theta notation.

Prove that log(3𝑛^3+ 2𝑛 + 17) = Θ(log(15𝑛^5+ 7𝑛^4 − 2))

I thought of simply raising both sides to the power of 2 and being left with the expressions themselves but I am not 100% this the right step towards the solution and I am honestly kind of lost.

I also know from the notation that I am looking for a solution that can satisfy the equation of:

c1(g(n))<=f(n)<=c2(g(n)), where c is a constant.

Upvotes: 0

Views: 340

Answers (1)

OmG
OmG

Reputation: 18838

Easy to prove:

n^2 <3n^3 + 2n + 17 < 5n^5 + 7n^4 -2 < n^6 for n > 10 
=> 2 log(n) < log(3n^3 + 2n + 17) < log(5n^5 + 7n^4 -2) < log(n^6) = 6 log(n)

As both of log(3n^3 + 2n + 17) and log(5n^5 + 7n^4 -2) are between a constant factor of log(n), you can conclude that log(3n^3 + 2n + 17) ⊂ Θ(log(5n^5 + 7n^4 -2)) and vice versa.

Upvotes: 1

Related Questions