# 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.

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$.
• @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