# Big-O compared to a new Operator

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!

-

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<n_0$ because we ensured the $c$ was big enough by comparing $g(n)$ and $f(n)$ for all $n\leq n_0$.

-
He said $f$ and $g$ are positive. –  jpalecek Nov 3 '12 at 18:51
Right, then it should work. –  Max Morin Nov 3 '12 at 18:52
@Max Morin can you explain me your method? What do you mean by the biggest of old c? How does pick the biggest number between those help me? –  SyndicatorBBB Nov 3 '12 at 18:54
@Guy I updated the answer, it should be very clear now. If not, you should think more about the problem. –  Max Morin Nov 3 '12 at 19:02
Trying to figure it out. Thank you ! –  SyndicatorBBB Nov 3 '12 at 19:02

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

-
These are generic function, how can I compute c? –  SyndicatorBBB Nov 3 '12 at 18:55

@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.

Oops. As you noted, you should divide by $g(n)$, not by $f(n)$. I shall correct my answer. –  Max Morin Nov 3 '12 at 19:36