Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

So, I initially proved the theorem that if $a != b^d$ and $n$ is a power of $b$, then $f(n) = C_1n^d + C_2n^{log_b a}$, where $C_1 = b^dc/(b^d − a)$ and $C_2 = f(1) + b^dc/(a − b^d )$.

This is seen here, for those who are interested: proof

What I want to know is how to show that if $a > b^d$, then $f(n)$ is $O(n^{log_ba})$?

Thank you!

share|cite|improve this question
How do you get $f(n)=af(n/b)+cn^d$ in the beginning of your inductive step ? – Dolma Apr 24 '13 at 20:07
Do you think that is wrong? – tekman22 Apr 24 '13 at 21:15
I didn't say it's wrong, just that I don't understand where it comes from. The only thing you know about the function $f$ is from the lemma you're trying to prove. In other words, at that time of the proof the only thing you can use about $f$ is its value for $n=b^k$, you can't say anything about its value for $n=b^{k+1}$. However, you might have some other information about $f$ that I don't know about, but for now I really don't see how you could possibly get this relation having no other information than what's in your post. – Dolma Apr 24 '13 at 21:26
Wow, well if it changes things, that shouldn't be $a! = b^d$ it should be $a$ $!=$ $b^d$.. – tekman22 Apr 24 '13 at 21:53
@Dolma Here is the image showing the proof in its entirety. Please let me know if there is something that appears wrong from this: – tekman22 Apr 24 '13 at 21:57

If $a > b^{d}$ then $\log_{b}a > \log_{b}b^{d} = d$.

Hence $n^{d} < n^{\log_{b}a}$

and so

$C_{1}n^{d} + C_{2}n^{\log_{b}a} < (C_{1} + C_{2})n^{\log_{b}a}$,

so $f(n)$ is $O(n^{\log_{b}a})$.

share|cite|improve this answer

Your Answer


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.