Issue

This Content is from Stack Overflow. Question asked by apbassett

Say I need to calculate the time complexity of a function
1⁶+2⁶+3⁶+…+n⁶. I am pretty sure this would be O(n⁷), but I only figure that because I know that Σi from i=0 to n is in O(n²). I cannot find a simple closed-version formula for a summation of i^k. Can anyone provide more detail on how to actually calculate the time complexity?

Thanks!

Solution

An easy proof that it’s Θ(n⁷) is to observe that:

1⁶+2⁶+3⁶+…+n⁶ <= n⁶+n⁶+…n⁶ = n⁷

(replacing all numbers with n makes the sum larger).

and

1⁶+2⁶+3⁶+…+n⁶ >= (n/2+1)⁶+…+n⁶ >= (n/2)⁶+(n/2)⁶+…+(n/2)⁶ = n⁷/2⁷

(in the first step, we discard the terms less or equal than n/2, and in the second step we replace all numbers with n/2. Both steps reduce the sum). (Note: I’ve assumed n is even, but you can extend to odd n with a bit of minor fiddling around).

Thus 1⁶+2⁶+3⁶+…+n⁶ is bounded above and below by a constant factor of n⁷ and so by definition is Θ(n⁷).

As David Eisenstat suggests in the comments, another proof is to consider the (continuous) graphs y=x⁶ and y=(x+1)⁶ from 0 to n. The area under these curves bound the sum below and above, and are readily calculated via integrals: the first is n⁷/7 and the second is ((n+1)⁷-1)/7. This shows that the sum is n⁷/7 + o(n⁷)

This Question was asked in StackOverflow by apbassett and Answered by Paul Hankin It is licensed under the terms of CC BY-SA 2.5. - CC BY-SA 3.0. - CC BY-SA 4.0.