Search code examples
iterationarray-algorithms

Recurrence iteration method solve

hi i have this recurrence: how to solve? a) Solve the following recurrence using the iteration method and give an asymptotic running time: T(0)=0 and T(n)=10 +T(n-1), for n ≥ 1

Solution

  • You can use dynamic programming technique to iteratively solve the problem:

    define results[n+1];
results[0] = 0;

for (i = 1; i < n + 1 ) {
      set  results[i] to 10 + results[i-1] 
}

Tn = results[n];

    Running time for the above algorithm will n.