2
$\begingroup$

There is a lot of explanation about big O, but I'm really confused about this part.

Acoording to the definition of Big-O, in this function

$$f (n) \le c g(n), \quad \text{for } n \ge n_0$$ $f (n)$ is $O(g(n))$.

But a description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function.

So for example 34 is a upper bound for the set $\{ 5, 10, 34 \}$.

So in this graph, how is $f(n)$ in $O(g(n))$ because if I get the upper bound of $g(n)$ function its value would be different than what is mentioned here for $n\ge n_0$.

enter image description here

$\endgroup$
4
$\begingroup$

I think you're confused about the notion of upper bounds for a function. We're not trying to compute an upper bound for the function $f$ in the sense of saying that, e.g., $f(n) \leq 45$ for all $n$ (or all $n$ greater than some $n_0$). Rather, we're trying to say that, for all $n>n_0$, the value (number) $c\,g(n)$ is an upper bound for the value $f(n)$. The graph indicates this informally (since it only shows what happens for some unstated but limited range of values of $n$).

$\endgroup$

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.