Thread replies: 5
Thread images: 1
Thread images: 1
I need help with Big-O notation proofs.
I understand that I need to find some constant C where f(n) < c x g(n) when n > k.
I wanted to find a sure way of finding this constant C when completing this proof so I know 100% that my proof is correct (I need this assurance to ease my anxiety post exam).
I am struggling to find anything on the internet. I read something about using L'Hospital's rule using limit of f(n)/g(n) as x -> infinity to find constant C that can be used in Big-O. Could someone please explain this to me and help me find a C everytime? (k is easy to find once I get how to find C)
>>
*L'Hopital's
Before anyone freaks out
>>
Thread theme:
https://www.youtube.com/watch?v=s7_Od9CmTu0
>>
>>366019
There are multiple C's that work. For instance, on 4x^3 + 3x^2, you could just take 4+3=7 and use it as C. k would be found via
7x^3 = 4x^3 + 3x^2
3x^3 = 3x^2
3x = 3
x = 1
Then say it's O(n^3) using C=7 and k=1, which is trivial to verify via inspection. But you can also look at the limit of
(4x^3 + 3x^2)
-------------------
........x^3
As x goes to infinity. First we cancel out the extra x^2, so it's just (4x + 3)/x. That 3 means nothing once x is huge, so it's really just 4x/x, which is 4 as x grows. What this means is that if I have a C of 4.00001, cubing that tiny little fractional bit at the end results in a greater value than the 3x^2 term once x is big enough. In our case, it'd be x=3/.00001 = 300000, which is huge but nothing compared to infinity. So in general, if a function's highest degree is N you can trivially say it's O(x^N).
>>
>>366036
Cheers anon. I understand now.
Thread posts: 5
Thread images: 1
Thread images: 1