Series Summation to calculate algorithm complexity

Question

I have an algorithm, and I need to calculate its complexity. I'm close to the answer but I have a little math problem: what is the summation formula of the series

½(n⁴+n³) where the pattern of n is 1, 2, 4, 8, ... so the series becomes:

½(1⁴+1³) + ½(2⁴+2³) + ½(4⁴+4³) + ½(8⁴+8³) + ...

Answer 1

thanks to all of u.. the final formula which I was looking for (based on your works) was :

((1/15 2^(4(log2(n)+1))  +  8^(log2(n)+1)/7  -232/105)/2) + 1

this will gives the same result as the program which runs the algorithm

Answer 2

You're asking about

½ Ʃ ((2^r)⁴+(2^r)³) from r=1 to n

(Sorry for the ugly math; there's no LaTeX here.)

The result is 16/15 16ⁿ + 8/7 8ⁿ - 232/105

See http://www.wolframalpha.com/input/?i=sum+%282%5Er%29%5E4%2B%282%5Er%29%5E3+from+r%3D1+to+n .

You don't need the exact formula. All you need to know is that this is an O(16ⁿ) algorithm.

Answer 3

It might help to express n as 2^k for k=0,1,2...

Substitute that into your original formula to get terms of the form (16^k + 8^k)/2.

You can break this up into two separate sums (one with base 16 and one with base 8), each of which is a geometric series.

S1 = 1/2(16^0 + 16^1 + 16^2 + ...)

S2 = 1/2(8^0 + 8^1 + 8^2 + ...)

The J-th partial sum of a geometric series is a(1-r^J)/(1-r) where a is the initial value and r the ratio between successive terms. For S1, a=1/2, r=16. For S2, a=1/2, r=8.

Multiply it out and I believe you will find that the sum of the first J terms is O(16^J).

Answer 4

looks like your series does not converge ... that is, the summation is infinity. maybe your formula is wrong or you asked the question wrong.