How to describe an algorithm whose input size diminishes by 1 for each iteration To elaborate on the title: I have a recursive algorithm whose input is reduced by 1 for every iteration until the input size is 1.

1st iteration: n

2nd iteration: n-1

3rd iteration: n-2

4th iteration: n-3

.

.

.

nth iteration: n-(n-1)

How can I describe this in asymptotic notation?
On recursive algorithms, you need first to obtain the recurrence relation. Then you solve the recurrence to get the total time required by the algorithm.

Let $n$ be the input size. Let $f(n)$ be the time required in each recursive call. Let $b$ be the input size for the base case. A general recurrence relation might look like this  

$$
T(n) = T(n-1) + f(n)  \quad \quad \textrm{if } n &gt; b \\
T(n) = c \quad \quad  \quad \quad \quad \quad \quad \quad \;\ \textrm{if } n = b 
$$
where $c$ typically is a constant (because typically the base case takes constant time).

So, you need to figure it out the function $f(n)$, which is specific for each algorithm. For example, if $f(n)=n$ (e.g. a simple pass on a array), and assuming $b=1$ and $c=1$ (it is not a problem to assume $c=1$ if you are working with assymptotic notation) then

$$
T(n) = T(n-1) + n  \quad \quad \textrm{if } n &gt; 1 \\
T(n) = 1 \quad \quad  \quad \quad \quad \quad \quad  \textrm{if } n = 1
$$

Solving this recurrence, you have that $$T(n) = n + (n-1) + \ldots + 2 + 1 = \frac{n(n+1)}{2} = O(n^2)$$.