Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

  • Congratulations Mike Lewis on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

Complexity Analysis

Status
Not open for further replies.

Jokky

Technical User
Jun 22, 2006
2
US
I'm trying to figure out the meaning to the below line

f(n) is O(1)
 
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(n)=O(1) means that f(n) 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(n)=1/n.
 
Correction:
order of [red]f[/red](x) is not bigger than that of [red]g[/red](x)
 
Status
Not open for further replies.

Part and Inventory Search

Sponsor

Back
Top