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

Commit id: 1a60283ad476a87eac2fc82f280bbcf12939625d

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 by  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 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)$.