Hi,

Below is sctracted out from my lecture notes. Can someone please explain the steps below. I have no idea how to do proving.


Ex2: Given f(n)=60n^2+5n+1, g(n)=n^2, prove that 60n2+5n+1= Θ(n^2)

Proof:
60n^2+5n+1 ≤ 60n^2+5n^2+n2 = 66n^2 for all n ≥ 1
Hence, we can take k1 =66, and n1=1, and conclude that f(n) =O(n^2)
Since 60n^2+5n+1≥ 60n^2, for all n ≥ 1,
we can take k2 = 60, and n2=1, and conclude that f(n) = Ω(n^2)
Based on the above, we have 60n^2+5n+1= Θ(n^2)