1
$\begingroup$

I am trying to figure out some stuff here with Big O Notation. I mean I understand the concept of it and can generally be able to tell what the efficiency of something is, but I do not really understand how to find witnesses. Here is an example of one that I need to do. Can anyone help me understand this? Thanks in advance!

Example 1: $n^2$ is $O(0.001n^3)$.

Example 2: $25n^4 − 19n^3 + 13n^2 − 106n + 77$ is $O(n^4)$.

  • 1
    What do you mean by "witnesses"?2012-10-14
  • 1
    The definition you're using probably want you to find a pair $(N, c)$ s.t. for example $n^2 for all $n>N$. If you manage to guess a reasonable constant you can probably find an $N$ for it really easily here.2012-10-14
  • 0
    Note that the $0.001$ in $O(0.001n^3)$ (or any other constant inside an $O$-term) is meaningless, as $O(0.001n^3) = O(n^3)$.2012-10-14

2 Answers 2

1

HINTS: For (1), try $c=1000$. For (2), try $c=25+19+13+106+77$. In each case think about why I suggested those particular numbers. (Note that they’re not the only ones that work; anything bigger works just as well, for instance. But they are the most obvious ones to try.)

  • 1
    Obviously they are simply the coefficients of the equations, which of course makes them obvious. But is that a safe assumption for most equations?2012-10-14
  • 0
    @MZimmerman6: The absolute values of the coefficients, actually. For polynomials, yes: that’s how you prove the general theorem that if $p(x)$ is a polynomial of degree $n$, then $p(x)$ is $O(x^n)$.2012-10-14
  • 1
    Okay, I understand that point then, but I guess I am just unsure what a "witness" tells me. It does not seem to give me valuable information.2012-10-14
  • 0
    And also it is asking about a value of k for the witness as well. So what is the other term, I know c but what is k2012-10-14
  • 0
    @MZimmerman6: The fact that you can produce witnesses at all gives you valuable information: it tells you something about the rate of growth of your function. That is, if you can produce witnesses $c$ and $N$ such that $|f(n)|\le c|g(n)|$ for all $n\ge N$, you’ve shown that $f$ is $O(g)$; and if $g$ is a nice, well-behaved function, especially one that doesn’t grow too fast, this tells you that $f$ behaves reasonably well too, at least in terms of rate of growth.2012-10-14
  • 0
    @MZimmerman6: Your $k$ is what Max Morin and I have called $N$: it’s how far out you have to go before you can be sure that $|f(n)|\le c|g(n)|$. Example: $100n\le n^2$ for all $n\ge 100$, so $c=1$ and $k=100$ are witnesses to the fact that $100n$ is $O(n^2)$. It’s also true that $100n\le100n^2$ for all $n\ge 1$, so $c=100$ and $k=1$ work equally well as witnesses to this fact. In both of your problems finding a usable $k$ is very easy if you use the values of $c$ that I suggested.2012-10-14
  • 0
    Oh okay, I think I get it now. Thank you so much!2012-10-14
  • 0
    It seems like that for most simple cases, either k or c will be 1, and the other will be the dominant coefficient of the function.2012-10-14
  • 0
    @MZimmerman6: You’re welcome! And yes, in simple cases there’s often an easy choice of $c$ and $k$ that makes one of them $1$.2012-10-14
0

I'm not sure what it means to find witnesses, but nevertheless:

  1. $n^2 = o(n^3)$, as well as $O(n^3)$ since $\lim_{n \to \infty}\frac{n^2}{0.001 n^3}=0$.

2.Do the same with the second expression: $\lim_{n \to \infty} \frac{a n^4 +b n^3 + c n+d}{s n^4} = \frac{a}{s}+o(1)=O(1)$ where $a,b,c,d,s$ are some constants.

  • 0
    $n^2$ is both $O(n^3)$ and $o(n^3)$. In fact, if $f\in o(g)$, then $f\in O(g)$.2012-10-14
  • 0
    corrected accordingly2012-10-14