Complexity Analysis

[Jokky]

I'm trying to figure out the meaning to the below line

f is O(1)

 

[cpjust]

http://www.cs.wisc.edu/~hasti/cs367-common/notes/COMPLEXITY.html

We express complexity using big-O notation. For a problem of size N:
- a constant-time method is "order 1": O(1)
- a linear-time method is "order N": O(N)
- a quadratic-time method is "order N squared": O(N2)

 

[mingis]

It is a mathematical order notation. Big O notation f(x)=O(g(x)) means, that functions f() and g() are of the same order, i.e., both linear, both quadratical, both exponential etc. More exactly it means, perhaps, that order of g(x) is not bigger than that of f(x). f=O(1) means that f is approximatelly a constant (well, not exceeds some constant limits independent of n). It could be any function convergent to constant or vanishing function like f=1/n.

http://en.wikipedia.org/wiki/O-notation

 

[mingis]

Correction:
order of [red]f[/red](x) is not bigger than that of [red]g[/red](x)