Array list: number

From Algowiki
Jump to: navigation, search

Algorithmic problem: Ordered sequence: number

Prerequisites:

Type of algorithm: loop

Auxiliary data:

  1. A pointer [math]p[/math] of type "pointer to array list item of type [math]K[/math]".
  2. A counter [math]c \in \mathbb{N}_0[/math].

Abstract view

Invariant: After [math]i \ge 0[/math] iterations:

  1. The pointer [math]p[/math] points to the array list item at position [math]i+1[/math] (or is void if there is no such item).
  2. The value of [math]c[/math] is the sum of the values n of all array list items at positions [math]1,...,i[/math].

Variant: [math]p[/math] is moved one step forward so as to point to the next array list item.

Break condition: It is [math]p=[/math] void.

Induction basis

Abstract view: Initialize [math]p[/math] so as to point to the first array list item.

Implementation:

  1. Set [math]p:=[/math]first.
  2. Set [math]c:=0[/math].

Proof: Nothing to show.

Induction step

Abstract view: Add the number of elements in the current array and then go forward.

Implementation:

  1. If [math]p=[/math]void, terminate the algorithm and return the value of [math]c[/math].
  2. Otherwise:
    1. Set [math]c:=c+p[/math].n.
    2. Set [math]p:=p[/math].next.

Correctness: Nothing to show.

Complexity

Statement: Linear in the length of the sequence in the worst case (if the arrays of all array list items have identical lengths).

Proof: Obvious.

Further information