week of march 19, 2014 csc148h1 winter 2014

 topic: Runtime analysis:
The binary search algorithm leads to the next question, how do you calculate the runtime of an algorithm?
We use O(n) as a mathematical function to represent the runtime.
The following are example models (which can be used in combination) the time a program could take to complete. Of course, time here is not measured in seconds (what if i have a better computer than you?) but in steps for n inputs.
The bellow mathematical models (stolen from the lecture slides) are very similar to the functions learned in high school math.
All these models (graphically) share the same "break even point" where a given n input produces the same runtime, but each function behaves arbitrarily different as the input becomes larger and larger.
To conclude, given lots and lots of input, with many many different methods of writing the code, the efficiency of the code should be kept in mind with the O(n) models.

constant:

c

2

R

+

(some p ositive numb er)

logarithmic:

c

log

n

linear:

cn

(probably not the same

c

)

quadratic:

cn

2

cubic:

cn

3

exp onential:

c

2

n

horrible:

cn

n

or

cn

!

Where n is the input, and O(n) represent the "Worst case running time" of the code.