This letter presents computationally efficient time-updating algorithms of the recent Iterative Adaptive Approach (IAA) spectral estimation technique. By exploiting the inherently low displacement rank, together with the development of suitable Gohberg-Semencul (GS) representations, and the use of data dependent trigonometric polynomials, the proposed time-recursive IAA algorithm offers a reduction of the necessary computational complexity with at least one order of magnitude. The resulting complexity can also be reduced further by allowing for approximate solutions. Numerical simulations together with theoretical complexity measures illustrate the achieved performance gain.