0
$\begingroup$

I'm trying to figure out a new operator compared to the Big O.

Suppose we have two positive functions, $f(n)$ and $g(n)$ then we say that $f(n) = O^*(g(n))$ if there exists a constant $ c > 0 $ such that $f(n) \le c(g(n)) $ for every integer $ n \ge 1 $

It is very similar to the BigO definition but you are a little bit more restricted here because you can't choose $n_0$.

I'm trying to prove that if $f(n) = O(g(n))$ then $f(n) = O^*(g(n))$

Here is what I got so far:

By the definition of BigO we know that if $f(n) = O(g(n))$ then there exist $n_0, c > 0$ such that $f(n) \le c(g(n))$ for every integer $n \ge n_0$

Now I set this $n_0$ to be 1 to apt the definition of $O^*$, but I can't figure out how to determine my $c$.

Can please someone give me an hint? Thanks!

3 Answers 3

2

You could pick the biggest of the old $c$ (the one that works for all $n>n_0$) and $f(1)/g(1), f(2)/g(2),\dots, f(n_0)/g(n_0)$ for your new $c$, but you're in trouble if $g(n)=0$ for some $n$ and $f(n)$ are not. This new $c$ will be big enough to ensure that $f(n)\leq c g(n)$ for all $n\geq n_0$ (because this was true for the old $c$, and this new $c$ is at least as big), and also for all the $n because we ensured the $c$ was big enough by comparing $g(n)$ and $f(n)$ for all $n\leq n_0$.

  • 0
    Okay. It is much more clear now. Thank you for your help!2012-11-03
1

Try computing th $c$ from all the values of $f(n)$, $g(n)$ for $n.

  • 0
    These are generic function, how can I compute c?2012-11-03
0

@MaxMorin I'v responded here to be more clear.

The idea of picking $g(1)/f(1),g(2)/f(2),…,g(n_0)/f(n_0)$ isn't clear to me at all.

In order to understand you I picked two random concrete function: $f(n) = n$ and $g(n) = n+1$.

So according to your method I can find the "biggest" new $c$ by picking the maximum of these $g(1)/f(1),g(2)/f(2),…,g(n_0)/f(n_0)$ values.

As far as I understand I could pick $c$ by dividing the inequality $f(n) <= c(g(n))$ by $g(n)$ not by $f(n)$.

I'm just trying to understand how did you understand that dividing $g(i)$ by $f(i)$ allows you to extract the biggest $c$.

Let's see few of them :

$g(1)/f(1) = 1/2$

$g(2)/f(2) = 2/3$

....

Last but not least you somehow have asserted there is a relation between the old $c$ and the new $c$, how comes?

Sorry for the inconvient but I just can't figure it out.

Thanks in advance.

  • 0
    Oops. As you noted, you should divide by $g(n)$, not by $f(n)$. I shall correct my answer.2012-11-03