I really don\'t understand how to find the big O of a function, including how to
ID: 2942817 • Letter: I
Question
I really don't understand how to find the big O of a function, including how to find witnesses. I've spent a good 2 days reading my text book and trying to do the questions but I just don't understand it.
Would someone please explain how to find the big O of a function and how to find witnesses in the simplest, easiest terms without all that mathematical jargon. Please provide step by step examples. Thanks
For example:
"Use the definition of big-oh to prove that 12 + 22 + ... + n2 is O(n3)"
Explanation / Answer
The O stands for 'order', so the idea is to try and give a simple enough function (like polynomial, exponential etc) which captures the nature of growth of the given function, as the variable grows large, say.
For instance any polynomial in n of degree k is O(nk). This is so since as n goes to infinity, nl is much smaller in order than nk. More formally, nl/nk goes to zero as n goes to infinity. Hence the leading term alone dominates.
In teh example you had up there, note that k2<n2 for k<n. Hence 12+22+...+n2 < n2+n2+...+n2where the number of terms is n. Hence
12+22+...+n2 < n2(n) = n3. Hence 12+22+...+n2 = O(n3).
Hope this helps.