# Computational Complexity.

• May 22nd 2010, 08:33 PM
Haven
Computational Complexity.
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?
• May 22nd 2010, 10:25 PM
CaptainBlack
Quote:

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?

Let $\displaystyle f(n)$ be the time complexity of adding an element to the end of a list of length n. Then the complexity of adding n elements to a null list is:

$\displaystyle F(n)=f(0)+f(1)+..+f(n-1)$

Now suppose $\displaystyle f(n)=kn+c$, then:

$\displaystyle F(n)=k(0+1+..+(n-1))+cn=k\frac{n(n-1)}{2}+cn\in O(n^2)$

CB
• May 24th 2010, 06:23 PM
Haven
is what I did right?