Running time of this algorithm?

Question

k ← 1
for i ← 1 to n do
    while k < 9i do
        k ← k + 1
        x ← x^2

 “← ” denotes the assignment statement. The scope of and nesting loops is indicated
by the indentation.

Why is the runtime of this algorithm only $\theta$(n)? I thought the second loop would iterate 9 * i times so it would be $\theta(n^2)$.

Answer 1

Note that the inner loop always runs exactly $9$ times (... because $k$ is not reset to $1$ in the outer loop) except the first time, when it only runs $8$ times, since $k$ does not start at $0$.