Summations while analyzing algorithms.

**Diligo** · November 2nd 2012, 02:08 PM

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

**TheSaviour** · November 2nd 2012, 03:15 PM

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?

Thread: Summations while analyzing algorithms.

LinkBack

Thread Tools

Display

Summations while analyzing algorithms.

Re: Summations while analyzing algorithms.

Similar Math Help Forum Discussions

analyzing the graph

Analyzing q further

Analyzing multidimensional input

analyzing a function

Analyzing a graph

Search Tags