BigO, Time Complexity

Time Complexity T(n)
http://planetmath.org/encyclopedia/TimeComplexity.html
- O(n2) and O(n3) are both polynomial time complexity classes, similarly O(2n) and O(3n) are exponential time complexity classes.
- All comparison-based sorting has time complexity no better than O(nlogn) , where n is the number of elements to be sorted.

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=complexity1
- How fast does the maximum runtime grow when we increase the input size?
- the worst possible case
- the input size is the length of the array/string, when talking about graph problems, the input size depends both on the number of vertices (N) and the number of edges (M), etc.
- worst of these inputs (i.e. theone that causes the algorithm to do the most steps).

E.g. if f (N) = $ \Theta$(N), we call the algorithm linear. More examples:

* f (N) = $ \Theta$(log N): logarithmic
* f (N) = $ \Theta$(N2): quadratic (bubble-sort)
* f (N) = $ \Theta$(N3): cubic multiply two nxn matrices
* f (N) = O(Nk) for some k: polynomial
* f (N) = $ \Omega$(2N): exponential

http://www.cs.odu.edu/~toida/nerzic/content/function/growth_files/summary.gif

For graph problems, the complexity $ \Theta$(N + M) is known as "linear in the graph size".

http://www.leda-tutorial.org/en/official/ch02s02s03.html
The number of (machine) instructions which a program executes during its running time is called its time complexity in computer science. This number depends primarily on the size of the program's input, that is approximately on the number of the strings to be sorted (and their length) and the algorithm used. So approximately, the time complexity of the program “sort an array of n strings by minimum search” is described by the expression c·n2.

http://en.wikipedia.org/wiki/Big_O_notation#Example_2

n=2^k, k = log2n

In typical usage, the formal definition of O notation is not used directly; rather, the O notation for a function f(x) is derived by the following simplification rules:
* If f(x) is a sum of several terms, the one with the largest growth rate is kept, and all others omitted.
* If f(x) is a product of several factors, any constants (terms in the product that do not depend on x) are omitted.

http://pages.pacificcoast.net/~cazelais/222/big-o.pdf
f(x) = (x2 + 5 log2 x)/(2x + 1) is O(x).
f(x) = (x + 5) log2(3x2 + 7) is O(x log2 x).
f(x) = 4x2 − 5x + 3 is O(x2).