Computational Complexity.

**Haven** · May 22nd 2010, 08:33 PM

It has been a while since I've used big- $\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:
$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 $\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 $i^{th}$ element, we must scan through $i-1$ elements. So the entire process takes:
$\sum_{i=0}^{n-1} i = \frac{n(n-1)}{2} \approx \mathcal{O}(n^2)$
Am I right?

**CaptainBlack** · May 22nd 2010, 10:25 PM

Originally Posted by Haven

It has been a while since I've used big- $\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:
$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 $\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 $i^{th}$ element, we must scan through $i-1$ elements. So the entire process takes:
$\sum_{i=0}^{n-1} i = \frac{n(n-1)}{2} \approx \mathcal{O}(n^2)$
Am I right?

Let $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:

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

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

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

CB

**Haven** · May 24th 2010, 06:23 PM

is what I did right?

Thread: Computational Complexity.

LinkBack

Thread Tools

Display

Computational Complexity.

Similar Math Help Forum Discussions

[SOLVED] complexity theorie, deterministic turing-machines, time complexity

Computational Complexity

Computational Algebra Programs

Computational Geo

Non computational proof sought

Search Tags