Find Complexity of S(n) = S(n-1) + n^2.5

[Grouchy187]

I need to do this problem but I get stuck halfway through,

Homework Statement

Find complexity of S(n) = S(n-1) + n^2.5 for n > 1 and where S(1) = 2

Homework Equations

The Attempt at a Solution

What I did so far..

S(n) = S(n-1) + n^2.5
S(n-1) = S(n-2) + (n-1)^2.5
S(n-2) = S(n-3) + (n-2)^2.5

so following this pattern...

S(3) = S(2) + 3^2.5
S(2) = S(1) + 2^2.5

then canceling,

S(n) = S(1) + 2^2.5 + 3^2.5 + ... + (n-2)^2.5 + (n-1)^2.5 + n^2.5

So basically, it is the Summation of n^2.5

But I do not know how to get a equation from that in terms of n. Any help would be appreciated.

 

[KataKoniK]

Thank you for sharing your progress on this problem. It seems like you have a good understanding of the pattern in the equation and how to approach finding the complexity. To get an equation in terms of n, you can use the formula for the sum of a geometric series, which is Sn = (a(1-r^n))/(1-r), where a is the first term and r is the common ratio. In this case, a = 2 and r = 1.5, since each term is being multiplied by 1.5. So the equation for the complexity would be S(n) = (2(1-1.5^n))/(1-1.5). I hope this helps you complete your solution. Keep up the good work!