使用Master方法解决复发

Question

我正在尝试解决一个复发关系，以找出我写的算法的复杂性。这是等式..

t（n）= t（n-1）+θ（n）

，我发现O（n2）的答案，但我不确定我是否正确。有人可以确认吗？

更新：如果等式是t（n）= t（n-1）+θ（nlogn）是什么？它仍然是o（n2）吗？

Answer 1

It is O(N)+O(N-1)+...+O(1) = O(N*(N+1)/2). So yes, the total complexity is quadratic.

Answer 2

Yes, you guess it right.

However, the form of the recurrence doesn't fit with Master method. Since you have guessed the bound correctly, substitution method is more suitable here.

Now your job is finding two constants c and n0 to prove that:

T(n) <= c*(n^2) forall n >= n0