-1
$\begingroup$

$f(n) = 3n+3$ ;
$f(n) = O(n)$
By definition :
$3n+3 \leq c_1.n$
By dividing both side by $n$
$3+\frac{3}{n} \leq c_1$
means we are getting constant range for $c_1$ for any $n$. Again it shows $c_1$'s value must be greater than $3$ at any cost.
e.g. if we take $c_1$'s value 3.5 so $n$'s value will be $6$.
Now if we plot graph ( Because I want to learn this concept by understanding graph )
$c_1.g(n)$ graph goes below of $f(n)$ graph. I have taken following values for both functions :
$f(n)=3n+3$

$ \begin{matrix} n & f(n)\\ 1 & 6\\ 2 & 9\\ 3 & 12\\ -2 & -3 \end{matrix} $

for $g(n) = 3.5n$
$ \begin{matrix} n & g(n)\\ 1 & 3.5\\ 2 & 7\\ 3 & 10.5\\ -2 & -7 \end{matrix} $

If we plot graph by these values it doesn't bind $f(n)$ i.e. $3n+3$ above by the value of $g(n)$ i.e. $3.5n$
Can anyone explain me this concept by graph ?

$\endgroup$
  • $\begingroup$ All that matters is the asymptotic behaviour as n goes to infinity. $\endgroup$ – Oli Charlesworth Jul 25 '13 at 12:25
  • 4
    $\begingroup$ Can you try to clean up the formatting of your question and make it a bit more obvious what you're asking? $\endgroup$ – jmite Jul 25 '13 at 16:37
  • $\begingroup$ To elaborate on @OliCharlesworth, since n is going to infinity, looking at n=-2 makes no sense; you need to look at extremely large n. For example, you find that in your example, you need n to be at least 6. But the largest n you try is 3, and then you wonder why it doesn't work. $\endgroup$ – Teepeemm Jul 26 '13 at 12:33
  • 1
    $\begingroup$ Don't.. $\endgroup$ – Raphael Jul 29 '13 at 8:03
  • $\begingroup$ 1. Don't. 2. See here. $\endgroup$ – Raphael Aug 5 '13 at 20:29
3
$\begingroup$

Here are a picture and some description:

The formal definitions associated with the Big Oh notation are as follows:

• f (n)= O (g (n)) means c · g (n)isan upper bound on f (n). Thus there exists some constant c such thatf (n) is always ≤ c · g (n), for large enoughn (i.e. , n ≥ n0 for some constant n0 ).

• f(n)=Ω(g (n)) means c · g (n) is a lower bound onf (n). Thus there exists some constant c such that f (n) is always ≥ c · g (n), for all n ≥ n0.

• f (n)=Θ(g (n)) means c1 · g (n) is an upper bound on f(n) and c2 ·g(n) is a lower bound on f (n), for all n ≥ n0 . Thus there exist constants c1 and c2 such that f(n) ≤ c1 · g(n) and f(n) ≥ c2 · g (n). This means that g(n) provides a nice, tight bound on f(n). enter image description here

You can find more details in the Chapter 2 of The Algorithm Design Manual,Steven S. Skiena.

$\endgroup$
  • 2
    $\begingroup$ This is all correct (and useful if you're looking for a basic understanding of the concept), but it isn't too difficult to come up with examples (e.g., log[log[x]], e^{x/1000}) where n0 is so big that you won't find it unless you already know the answer. $\endgroup$ – Teepeemm Jul 26 '13 at 13:30
2
$\begingroup$

The big $O$ notation describes the limiting behavior of a function. That mean the property you are looking for is true for $n$ large enough.

$g(n)$ may be smaller than $f(n)$ for small $n$ but as $n$ goes to the infinite $g(n)$ will at some point always be greater than $f(n)$.

What the big $O$ notation look like on a graph is: if you look at the two right end of both function $f(n)$ is lower than $g(n)$. But it's hard to look at infinity with a graph...

$\endgroup$
2
$\begingroup$

From introduction to the design and analysis of algorithms:

a function $t(n)$ is $O(g(n))$ if $t(n)$ is bounded above by some constant multiple of $g(n)$ for all large $n$.

So, $t(n) \le cg(n) \quad \text{for all $n>n_o$}$

big O

This image is from here.

Edit: I meant to say that the referenced book, as well as the webpage have graphical explanations for Oh, Omega, and Theta notation.

$\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.