announcements‎ > ‎

2016-01-04

posted Jan 4, 2016, 7:20 AM by Samuel Konstantinovich   [ updated Jan 4, 2016, 7:56 AM ]
Baron's Review Here: 
http://marge.stuy.edu/~konstans/
(slightly dated, but most of the stuff is super effective)


Big O notation is used to measure the runtime of functions as the input grows. 

When a function is O(n) that means that when you increase the input size, the runtime increases in a linear fashion. Double input size means double* the runtime . 

When a function is O(n^2) that  means that when you increase the input size, the runtime increases in a quadratic fashion. Double input size means FOUR times* the runtime.

O(c^n) is exponential. Increase the input size by one, and the runtime increases by a factor of c times*. 

* All of these can be off by a constant factor that we don't care about, as long as the pattern holds. So if you double the input and it triples the runtime, that is still linear.

Also note that two data points are not sufficient to determine the runtime growth. We really need 3 or more data points to see.



Formal Definition:

Lets think of x as the input size of a function.

    You can say  f(x) is O(g(x))  as x approaches infinity

    IF AND ONLY IF:

    There exists some positive real constant M such that:

        f(x) <= M * g(x) 

Think of and f() and g() as the amount of work the function does, not the result of the actual function.



(we simplify g(x) in terms of a function of n as follows)

3x^2  is O(n^2)

230x  is O(n)

5*2^x  is O(2^n)

Remember we do NOT care about constants!

4x is still O(n)









Big O examples and more text:

https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
Comments