An interview question

I had an job interview, and the interviewer had a cool technical and language agnostic question.... He just put the focus on algorithms and their complexity.

The problem was: What is the original complexity of the following function, how to optimize it and what is the resulting complexity.

The function was a common box filter where each output pixel is the sum of the each input pixel around him in a KxK area. And just add some 'noise' in the reflexion he said that the 2-dimensional image was a WxH plane.

So let use some math notation to express that:

$$P\text{'}(x,y)=\sum _{i=\frac{-k}{2}}^{\frac{k}{2}}\sum _{j=\frac{-k}{2}}^{\frac{k}{2}}P(x+i,y+j)$$

Looking at that formula, the complexity is clearly O($$k^2$$).

Now let express P' iteratively:
$$\begin{array}{l}P\text{'}(x+1,y)=\sum _{i=\frac{-k}{2}}^{\frac{k}{2}}\sum _{j=\frac{-k}{2}}^{\frac{k}{2}}P(x+i,y+j)+\sum _{j=\frac{-k}{2}}^{\frac{k}{2}}P(x+1+\frac{k}{2},y+j)-\sum _{j=\frac{-k}{2}}^{\frac{k}{2}}P(x-\frac{k}{2},y+j)\\ \end{array}$$
or ....
$$P\text{'}(x+1,y)=P\text{'}(x,y)+\sum _{j=\frac{-k}{2}}^{\frac{k}{2}}P(x+1+\frac{k}{2},y+j)-\sum _{j=\frac{-k}{2}}^{\frac{k}{2}}P(x-\frac{k}{2},y+j)$$

So now the complexity is O(2k)! and if you use a k-vector store the sum of each column, and use that sliding window process, a correct implementation will be in O(k+1)