Time complexity from an arithmetic series

Question

I am attempting to find the complexity of an algorithm and I have noticed that the following pattern emerges:

Problem size of:

Problem size(1) = 1

Problem size(2) = 1 + 1

Problem size(3) = 2 + 1 + 1

Problem size(4) = 3 + 2 + 1 + 1

Problem size(5) = 4 + 3 + 2 + 1 + 1

Problem size(6) = 5 + 4 + 3 + 2 + 1 + 1

Problem size(7) = 6 + 5 + 4 + 3 + 2 + 1 + 1

Therefore I get the following recurrence relation I believe: T(n) = T(n-1) + (n - 1)

How do I convert this into a quadratic formula?

I have the following: ((n^2 - n) / 2) + 1 which I have done with trial and error, however how can I get a systematic way of solving this?

I have no idea which branch of maths this is, not sure if the tags are correct.

Answer 1

The sum $1+2+3+\cdots+n$ is a triangular number; there is a well known formula for them, which you seem to have rediscovered. Well done!

More generally, what you have is an aritmetic series (and then a trailing $+1$). The sum of an arithmetic series can be computed as the number of terms, here $n$, times the arithmetic mean of the first and last terms, here $\frac{1+n}2$. (This formula is sometimes known as Gauss's trick, due to a -- probably apocryphal -- story that Gauss used it to calculate $1+2+3+\cdots +100=5050$ as a schoolchild).

Answer 2

$$T_n =T_{n-1} + (n-1) \\ T_n = T_{n-2} + (n-2) + (n-1) \\ \vdots \\ T_n = T_1 + 1 + 2 + \ldots + (n-2) + (n-1)\\ T_n = 1 + \sum_{i=1}^{n-1}i \\ T_n = 1 + n(n-1)/2 $$

On the second line we replaced $T_{n-1}$ with an equivalent expression, found by plugging $n-1$ into the equation you gave: $T_{n-1}=T_{n-2} + ((n-1) -1)$. We continue this process until we have eliminated all of the unknowns, at which point we are left with a sum.