Solving recurrence relation: ()=(−1)+⋅(−1), T(1) = 0

Question

The following pseudo code checks whether all elements in a linked list are distinct.

boolean checkList( start)
{
     val = start.data;
     P = start.next;
     while (P!=null)
     {
          if (val == P.data)
               return false;
          P = P.next;
     }
     if (start.next != null)
         return checklist(start.next);
     else 
        return true;
}

The recurrence relation for this function is:

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

with the basic operation being

val == P.data

and the answer being

O(n^2)

I can't figure out the general case here or how it would lead to O(n^2).

Answer 1

The sum of integers from 1 to $n$ ends up quadratic:

$$\sum_{i = 1}^n i = \frac{n (n + 1) } { 2 } $$

So expanding out $T(n)$ gives you a quadratic, as Youem mentioned in his comment.