I'm currently studying this paper and I am trying to understand the complexity of the interpolate algorithm, which is supposed to be $O((l+m)^2)$.
So first the algorithm runs in $r$ steps where $r\leq l+m$. So I think the first $(l+m)$ factor comes from this.
Now I guess the most expensive step in the algorithm is the calculation
$$f_0(x,y)=f_0^q(x,y)-\Delta_0^{q-1}f_0(x,y) $$
where the $f^q_0(x,y)$ calculation boils down to calculating $a_i^q$ for some $a_i\in \mathbb{F}_{q^m}$ for an integer $m$ and prime power $q$. Now my questions is what is the complexity of this calculation?