# What is a basic definition for Big Oh, and it's component parts?

this is a question that somewhat straddles the boundaries of computer science (data structures and ). I'm mostly fine with data structures, until encountering big oh notation.. at which point my head exploded.

I think I understand by name some aspects of the mathematical definition found in http://courses.csail.mit.edu/6.042/spring12/mcs.pdf (page 473), namely asymptotics. I only understand from this definition after being hazy about asymptotics (and not fully having an understanding of logarithms, that something gets significantly large that beyond a point of equilibrium the value becomes increasingly infinitesimal as it moves to infinity.

what do the component parts of f = O(g) or lim sup f(x)/f(g) < infinity really mean? I know there are other definitions/explanations but they go very deep into the math. I need a simple, but comprehensive explanation so that I can start to understand the material.

## 1 Answer

The simplest way to think about the big O notations is such: Let $f,g$ be two functions, if $f(x)=O(g(x))$, then $g$ grows atleast as fast $f$.

An equivalent defintion (and a bit more intutive) of $limsup (f(x)/g(x))<inf$ is: $f(x)=O(g(x))$ if there are constants $x_0,c$ such that for every $x>x_0$ it follows $c*g(x)>f(x)$. Meaning, from some point $g$ "beats" $f$.

The following image can give you a preety good clue how two such functions might look like. • For those wondering, the image was created by Federico Reghe and is shown on the wikipedia page for Big-O notation. – Antonio Vargas Mar 1 '13 at 16:10
• so basically, there is some function on x for which it gets so large that the increase in performance will ultimately become 0 and even negative. – peter_gent Mar 3 '13 at 17:07
• A further question. What's the importance of the area beyond X(0) ? Does it mean complexity will rise beyond an acceptable rate ? – peter_gent May 14 '13 at 21:27
• @peter_gent The point $X_0$ has no significance as it depends on the constant $c$ which we are allowed to replace with a bigger one – Hagen von Eitzen Jul 29 '15 at 16:14