0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

big O function

$\endgroup$
  • $\begingroup$ For those wondering, the image was created by Federico Reghe and is shown on the wikipedia page for Big-O notation. $\endgroup$ – Antonio Vargas Mar 1 '13 at 16:10
  • $\begingroup$ 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. $\endgroup$ – peter_gent Mar 3 '13 at 17:07
  • $\begingroup$ A further question. What's the importance of the area beyond X(0) ? Does it mean complexity will rise beyond an acceptable rate ? $\endgroup$ – peter_gent May 14 '13 at 21:27
  • $\begingroup$ @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 $\endgroup$ – Hagen von Eitzen Jul 29 '15 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.