Results 1 to 2 of 2

Math Help - Summations while analyzing algorithms.

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    Earth
    Posts
    9

    Summations while analyzing algorithms.

    I'm learning about the analysis of algorithms and I'm encountering some steps in an explanation which I can't quite understand (log is a logarithm with base 2 in this context).

    c \log n + 1 + \sum_{i=0}^{n^2 - 1} (10 + 10 + \sum_{j=0}^{\frac{i}{\log n}} 20) \leq

    c \log n + 1 + \sum_{i=0}^{n^2 - 1} ( \sum_{j=0}^{1 + \frac{i}{\log n}} 20) \leq

    c \log n + 1 + \sum_{i=0}^{n^2 - 1} (20(2 + \frac{i}{\log n})) \leq

    The step from the second to third doesn't quite click, but it goes on:

    c \log n + 1 + 20 \sum_{i=0}^{n^2 - 1} (2 + \frac{i}{\log n}) \leq

    c \log n + 1 + 20 \sum_{i=0}^{n^2 - 1} 2 + 20 \sum_{i=0}^{n^2 - 1} \frac{i}{\log n}\leq

    The above step is a bit hazy too...

    c \log n + 1 + 40n^2 +  \frac{20}{\log n}\sum_{i=0}^{n^2 - 1} i\leq

    c \log n + 1 + 40n^2 +  \frac{20}{\log n}\frac{n^2(n^2 - 1)}{2}\leq

    c \log n + 1 + 40n^2 +  \frac{10n^4}{\log n}

    Which is a worst-case running time of O(\frac{n^4}{\log n})

    Basically I'm lacking insight into alot of the simplifications/reductions/steps taken to come to c \log n + 1 + 40n^2 +  \frac{10n^4}{\log n} I would very much appreciate some clarification on steps taken so I can apply this when I need to analyze algorithms myself
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Mar 2012
    From
    Unknown
    Posts
    29
    Thanks
    3

    Re: Summations while analyzing algorithms.

    Remember that sum_(i=0)^(r) a = a(r+1). Lots of the steps are simplified by this fact. Basically the sum over a term that doesn't depend on the index of the sum is unity plus the difference of its bounds times the term. By the way, are all of these steps really less than or equal to? Is it necessary to use less than or equal to in all of the steps?
    Last edited by TheSaviour; November 2nd 2012 at 03:25 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. analyzing the graph
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: September 12th 2012, 10:14 PM
  2. Analyzing q further
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: March 2nd 2010, 03:09 PM
  3. Analyzing multidimensional input
    Posted in the Calculus Forum
    Replies: 1
    Last Post: August 2nd 2009, 07:17 AM
  4. analyzing a function
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: January 5th 2008, 06:44 AM
  5. Analyzing a graph
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: November 26th 2007, 07:23 PM

Search Tags


/mathhelpforum @mathhelpforum