Find the order of a function

Question

What is the lowest order of the following function as n tends to infinity?

where a>1 and 0<p<1.

My answer: Since ln(1+x) <= x,

Therefore, f(n) = O(a^n). I am sure this is not a tight bound. I might be able to use to obtain a tighter bound, but I don't think it will improve the order. Any idea? Please let me know anything you think may be helpful.

Answer 1

Answer: O(n^2).

Proof:

f(n) = sum(i,log(pa^i+(1-p)))
     = sum(i,log(p*a^i(1+(1-p)/(pa^i))))
     =< sum(i,i*log(a)) + sum(i,log(p)) + sum(i,(1-p)/(pa^i))
     =< n*(n+1)*log(a)/2 + n*log(p) + (1-p)/p * 1/(1-1/a)

This estimate is optimal because all inequalities are actually asymptotic equivalences.

Note that this is much smaller than your exponential estimate.