$T(n)=T(n-1)+O(\log n)$ is $T(n)=O(n^2)$ or $T(n)=O(n \log n)$

Question

I have this Recurrence relation: $T(n)=T(n-1)+O(\log n)$

What is the solution? $T(n)=O(n^2)$ or $T(n)=O(n \log n)$

What I did is: I assume that $T(n)\le O(n^2)$

And that's bring me to $O(n^2)$, I'm right?
Or I have mistake?

Thank you!

Answer 1

This problem is easier to do by repeated substitution. Your answer is technically correct, but often times big-oh notation is used rather than big-theta notation and I assume that your task was to show a tight asymptotic bound i.e. big-theta.

$T(n)=T(n-1)+\Theta(\log(n))$ implies

$T(n)=T(n-2)+\Theta(\log(n-1))+\Theta(\log(n))$, repeating this we get:

$T(n)=T(0)+\sum\limits_{i=0}^{n-1}\Theta(\log(n-i))=T(0)+\Theta(\log(n!))=\Theta(n\log(n))$ by Stirling's approximation.