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.

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|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? –  stevenmadden 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$.. –  stevenmadden 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: gyazo.com/4dc761cba2cdeea403a30ef77cfa225b.png?1366840613 –  stevenmadden Apr 24 '13 at 21:57
show 4 more comments

1 Answer

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|improve this answer
add comment

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.