T( n) =T(n-1)+O(log n)$is T(n)=O(n^2)或T(n)=O(n log N)

Question

我有这样的递推关系: T( n) =T(n-1)+O(log )

解决办法是什么？T( n) =O(n^2)或T(n)=O(n log N)

我所做的是:我假设T(N)<=O(n^2)…

​

把我带到O(n^2)，我是对的？

还是我弄错了？(我从某人那里听说他得到了O(n log n)，如果我是对的，或者他是.)

谢谢!

Answer 1

如果T(n)<=T(n-1) +c log对某些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 因此: T(n) <= T(0) + sum_{i=1 .n} c log I= O(n log n) 但O(n^2)也是对的，但不那么具体，因为T(n) = O(n^2)是指 有一些a，m使得T(n)<=a n^2适用于所有n>=m