# Issue

*This Content is from Stack Overflow. Question asked by apbassett *

Say I need to calculate the time complexity of a function

**1 ^{6}+2^{6}+3^{6}+…+n^{6}**. I am pretty sure this would be

**O(n**, but I only figure that because I know that

^{7})**Σi**from

**i=0**to

**n**is in

**O(n**. I cannot find a simple closed-version formula for a summation of i

^{2})^{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.