TITLE: Solving recurrence relation: ()=(−1)+⋅(−1), T(1) = 0
QUESTION [0 upvotes]: 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).

REPLY [1 votes]: 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.
{"set_name": "stack_exchange", "score": 0, "question_id": 2728240}