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

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

i have recurrence relation: t(n)=t(n-1)+o(log n)

what solution? t(n)=o(n^2) or t(n)=o(n log n)

what did is: assume t(n)<=o(n^2)...

and that's bring me o(n^2), i'm right? or have mistake? (i heard got o(n log n) , i'm curies if i'm right or him...)

thank you!

if t(n)<=t(n-1) + c log n c

=> t(n) <= t(n-2) + c log (n-1) + c log n

=> t(n) <= t(n-3) + c log(n-2) + c log(n-1) + c log n

thus: t(n) <= t(0) + sum_{i=1 .. n} c log = o(n log n)

but o(n^2) right less specific, since t(n) = o(n^2) means

there a, m such t(n)<=a n^2 n>=m

recursion big-o