Niclas Alexandersson edited b) Finding the solution.tex  about 10 years ago

Commit id: 3593c7822af445978c5683d3485c43c412e29e00

deletions | additions      

       

\end{algorithmic}  \end{algorithm}  At each point, the above algorithm has two choices; it can either take a horizontal step through the memory array by making another iteration in the loop, or take a vertical step through making a recursive call. The horizontal steps will always be in the same direction, and the same is true for the vertical steps. Therefore, the maximum number of steps which can be taken by the algorithm are is  $i + x$. Apart from the array initialisation, which takes $i$ time, all other operations in and outside the loop which are not recursive calls are constant time operations. Thus we get a runtime complexity of $\mathcal{O}(i+x)$.