Array list: number
Algorithmic problem: Linear sequence: number
Prerequisites:
Type of algorithm: loop
Auxiliary data:
- A pointer [math]\displaystyle{ p }[/math] of type "pointer to array list item of type [math]\displaystyle{ K }[/math]".
- A counter [math]\displaystyle{ c \in \mathbb{N}_0 }[/math].
Abstract view
Invariant: After iterations: The pointer points to the array list item at position (or is void if there is no such item). The value of is the sum of the values n of all array list items at positions . Variant: is moved one step forward so as to point to the next array list item. Break condition: It is void.
Induction basis
Abstract view: Initialize so as to point to the first array list item. Implementation: Set first. Set . Proof: Nothing to show.
Induction step
Abstract view: Add the number of elements in the current array and then go forward. Implementation: If void, terminate the algorithm and return the value of . Otherwise: Set .n. Set .next. Correctness: Nothing to show.
Complexity
Statement: Linear in the length of the sequence in the worst case (for a fixed value of ). Proof: Obvious.
Further information