Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer
    
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$.

share|improve this answer
    
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.

Thanks in advance.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.