How to solve: T (n) = T (n - 1) + n

Question

I managed:

T(n) = T(n - 1) + n = O(n^2) 

Now that I’ll find out, I’ve found that the border is very loose. Did I do something wrong or is it so?

Answer 1

Think of it this way:
In each "iteration" of recursion, you do O (n) work.
Each iteration has n-1 work, as long as n = base case. (I assume the base case of O (n) works)
Therefore, assuming that the base case is a constant independent of n, there are O (n) recursion iterations. If you perform n iterations of O (n), then O (n) * O (n) = O (n ^ 2).
Your analysis is correct. If you want more information about this recursion path, look into the recursive trees. They are very intuitive compared to other methods.

Answer 2

For your recursive relationship, you also need a base register.

 T(1) = c T(n) = T(n-1) + n 

To solve this problem, you can first guess the solution and then prove that it works using induction.

 T(n) = (n + 1) * n / 2 + c - 1 

Base register first. When n = 1, this gives c as required.

For other n:

  T(n) = (n + 1) * n / 2 + c - 1 = ((n - 1) + 2) * n / 2 + c - 1 = ((n - 1) * n / 2) + (2 * n / 2) + c - 1 = (n * (n - 1) / 2) + c - 1) + (2 * n / 2) = T(n - 1) + n 

So the solution works.

To get the guess first, note that your recurrence relation generates triangular numbers when c = 1:

 T(1) = 1: * T(2) = 3: * ** T(3) = 6: * ** *** T(4) = 10: * ** *** **** etc.. 

Intuitively, a triangle is about half a square, and constants can be ignored in a Big-O record, so O (n ^ 2) is the expected result.

Answer 3

The solution is quite simple for this. You must expand the recursion:

 T(n) = T(n-1) + n = T(n-2) + (n - 1) + n = = T(n-3) + (n-2) + (n-1) + n = ... = = T(0) + 1 + 2 + ... + (n-1) + n 

Here you have an arithmetic progression, and the sum is 1/2*n*(n-1) . Technically, you are missing the boundary condition here, but with any constant boundary condition you see that the recursion is O(n^2) .

Answer 4

It looks correct, but will depend on the base case T (1). Assuming you take n steps to get T (n) to T (0) and every time the n-term is somewhere between 0 and n for the average n / 2, so n * n / 2 = (n ^ 2) / 2 = O (n ^ 2).