-
April 11th, 2010, 12:37 AM
#1
How to do proofing
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)
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|