Results 1 to 3 of 3

Math Help - Computational Complexity.

  1. #1
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8

    Computational Complexity.

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Haven View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8
    is what I did right?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] complexity theorie, deterministic turing-machines, time complexity
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 19th 2011, 06:44 AM
  2. Computational Complexity
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 13th 2010, 07:48 PM
  3. Computational Algebra Programs
    Posted in the Math Software Forum
    Replies: 0
    Last Post: October 11th 2009, 11:49 AM
  4. Computational Geo
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: February 24th 2009, 07:47 AM
  5. Non computational proof sought
    Posted in the Geometry Forum
    Replies: 2
    Last Post: July 10th 2008, 05:16 PM

Search Tags


/mathhelpforum @mathhelpforum