0
$\begingroup$

From the definition of Big Oh, it states that there should be a function $g(x)$ such that it is always greater than or equal to $f(x)$. Or $f(x) \le cg(n)$ for all values of $n > n_0$. What I'm not able to understand is what is its importance in Big oh notation. Every question explains what is big-Oh and what how it uses useful .. But I'm not able to understand what is $c$ actually in big-oh. There might be answer which I'm not able to get it due to its technical jargon.

Can someone explain me this in simple terms?

$\endgroup$
4
$\begingroup$

Let's suppose the constant $c$ wasn't there: let's say that $f(n)=O'(g(n))$ if $f(n)\leq g(n)$ for all large enoun $n$. So, for example, $n=O'(n^2)$ and $\log n = O'(n)$, as you'd expect. But let's look at some functions whose growth rates are closer. First, let $f(n)=n+1$ and $g(n)=n$: well, $f(n)\neq O'(g(n))$ because $n+1 \not\leq n$ for all $n$. Similarly, $2n\neq O'(n)$. SO, we see that the constant $c$ is absolutely essential to the definition of $O(-)$: it just doesn't do what we want it to do if we remove it.

$O(-)$ measures the growth rate of functions ignoring constant factors. It gives you notation to say things like "$f$ is linear" or "$f$ is quadratic". When we say "$f$ is linear", we don't distinguish between, say, $f(n)=n$ or $f(n)=4n$ or $f(n)=2n+12$: we ignore the constants. The constant $c$ in the definition of $O(-)$ allows it to ignore multiplicative constants and additive terms.

$\endgroup$
  • $\begingroup$ "it just doesn't do what we want it to do if we remove it" -- citation needed. Maybe here or here? ;) $\endgroup$ – Raphael Apr 28 '15 at 9:30

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.