![]() ![]() Therefore the algorithm works correctly for $n=1$. This is exactly what the algorithm returns in this case (in line 2). Thus the array contains one element, $A$, and the sum of element(s) is also simply $A$. We prove the correctness of the algorithm sum1 by induction on $n = len(A)-first$.īase case ($n=1$): If $n=1$ then $first = len(A)-1$. The algorithm sum1 computes the sum of numbers in the array A. ![]() Now a correctness proof for sum1 could go as follows. Thus for sum1 we can take the size of this array as induction variable $n = len(A)-first$. It is not the actual input size that decreases, but the size of the subarray A. But for sum1 the situation is already more intricate. In this case indeed the size of the input decreases with every recursive call. Lets briefly consider the algorithm sum_splice. In an induction we will typically prove this byġ.) proving $P(n)$ for a base case (sometimes several base cases), i.e., to prove that P(1) holds, and thenĢ.) proving that if $P(n)$ holds for some $n$ (This is the induction hypothesis) that $P()$ then holds for the next natural number, i.e., that $P(n+1)$ holds.įor a recursive algorithm the statement $P(n)$ commonly is something like: The algorithm provides correct output for all inputs of size $n$. In a mathematical induction we want to prove a statement $P(n)$ for all natural numbers $n$ (possibly starting at an $n_0$, but lets assume for simplicity we are proving the statement for all $n \ge 1$). To prove the correctness of a recursive algorithm we use mathematical induction.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |