Explain Big O notation to me like I was a fucking moron

>>8825563

>like I was a fucking moron
>like

File: DVD1-Cover.jpg (291KB, 983x1445px) Image search: [Google]

291KB, 983x1445px

>>8825563
Big-O just says "processing time relative to the number of items you have to process won't rise any faster (on average) than a certain rate". If one algorithm has a larger big-O than another algorithm, that just means that the first algorithm is less efficient than the other one and will take longer to process the same number of items as the other one.

>>8825610
>remember, I'm a moron

tl;dr

>>8825610

Only asymptotically.

For example f(n) = 100000n is O(n).

Also big-O is <= not <. You're thinking of litte-o

f(n) is O(g(n)) if for some FIXED c, k > 0, all n >= n, f(n) <= c*g(n).

replace <= with < to get O(g(n)), > to get omega(g(n)), and >= to get Omega(g(n)), and = to get theta(g(n)).

Also, big-O doesn't necessarily mean algorithm, or even if it does mean algorithm, it is not necessarily the time complexity (it could be space). Big-O is just general assymptotic function bounding notation.

>>8825623
You are technically correct (which is the best kind of correct). However, see >>8825618. Most of the time, if you have to think about big-O, it'll be for execution time.

It tells you how much hand-waving you put into your numerical output

>>8825654

Only in terms of asymptotically though. When you have real-world things like caching, etc going through, everything goes to shit. Often times a linear array is going to outperform fancy stuff for most reasonable-sized inputs, even when it's O(n) vs O(logn) due to having to jump everywhere in memory vs read in a line.

And even without that, you still get algorithms with constants that will be bigger than logn terms for most sane values of n.

>>8825623
>Big-O is just general assymptotic [sic] function bounding notation.
I am not OM (original moron) but I guess this means that the Big-O definition should be expressible in analytic terms?
I mean,
>f(n) is O(g(n)) if for some FIXED c, k > 0, all n >= n, f(n) <= c*g(n).
shouldn't be too hard to convert into a statement about convergence of some tail filter.

>>8825825
>should be expressible in analytic terms?

It's often given in terms of limits where you have [math]\lim_{n\rightarrow\infty} \frac{f(n)}{g(n)}[/math] and see if it's 0, a constant or infinity

>>8825563
What is the big O running time of Kartatsuba algorithm

You have to find the clitoris.

>>8825831
[math]
\displaystyle \lim_{n \rightarrow \infty} \frac{f(n)}{g(n)}
[/math]