I came across this problem while studying which asks to consider a data structure where a sequence of n operations are performed. If the kth operation has a cost of k if it is a perfect square and a cost of 1 otherwise, what is total cost of the operations and what is the amortized cost of each operation.
I am having a bit of difficulty coming up with a summation formula that provides the definition of a perfect square where I can see what the sum yields. Any thoughts/advice?
The sum of i^2 from 1 to n can be calculated as n(n+1)(2n+1)/6. I found it in a math book, can't find a simple formula online. But check out http://mathworld.wolfram.com/Sum.html, formula (6).
To calculate this sum, let n be the square root of k, rounded down. The formula is proportional to n^3 which is sqrt(k)^3 = k^(3/2). This gives an amortized time of O(k^(3/2)).