Originally Posted by

**Haven** It has been a while since I've used big-$\displaystyle \mathcal{O}$. So i was wondering if I was analyzing this algorithm correctly.

So I am using a linked list, which is a non-indexed list. Each entry essentially "points" to the next one. The list is designed like this:

$\displaystyle a_1\rightarrow a_2 \rightarrow \dots \rightarrow a_n \rightarrow NULL $

This is an example, of a linked list of n elements. In order to add another element on to the end of the list we must scan through the entire list until we reach the end and then add the element

Obviously, adding an element is $\displaystyle \mathcal{O}(n)$

However, if I start with no elements, and I want to add n elements in sucession. I argue that to add the $\displaystyle i^{th}$ element, we must scan through $\displaystyle i-1 $ elements. So the entire process takes:

$\displaystyle \sum_{i=0}^{n-1} i = \frac{n(n-1)}{2} \approx \mathcal{O}(n^2)$

Am I right?