Antag vi ønsker at gemme en mængde af $n$ tal vha. hashing med linear probing i et array af størrelse $N$. Vi garanterer at arrayet altid er mellem 1/4 og 3/4 fyldt. Hvis der bliver færre end $N/4$ eller flere end $3N/4$ tal i mængden genindsætter vi alle tal i et nyt array af størrelse $2n$, dvs. det nye array er 1/2 fyldt. Angiv en potentiale funktion hvormed man kan vise at det totalle antal genindsættelser i hashtabellerne er amortiseret $O(1)$ per indsættelse og slettelse i mængden.

Rød-sorte søgetræer understøtter Insert og Delete på et træ med $n$ elementer i worst-case tid $O(\log n)$. Angiv en potentialefunktion hvormed man kan argumentere for at Insert tager amortiseret tid $O(\log n)$ og Delete tager amortiseret $O(1)$ tid.

Antag at en binær max-heap med $n$ elementer er gemt i de første $n$ indgange i et array af størrelsen $N$. Operationerne Insert og Extract-Max implementeres som for en standard binær max-heap, på nær Insert når $n=N$, hvor heapen først kopieres over i et nyt array af dobbelt størrelse $2N$, dvs. $N$ fordobles, hvorefter Insert operationen udføres som for en standard binær max-heap. Angiv en potentialefunktion hvormed man kan argumentere for at Insert tager amortiseret $O(\log n)$ tid og Extract-Max tager amortiseret $O(1)$ tid.

Betragt et array $A[0..N-1]$ af længde $N$, hvor hver indgang er enten 0 eller 1. $A$ opfattes som et binært tal med værdien $n$, hvor $n=\sum_{i=0}^{N-1} 2^i\cdot A[i]$. Operationen Inc$(A)$ øger værdien af $n$ med 1 ved at flippe $A[0],A[1],...$ indtil det første $A[i]$ flippes fra 0 til 1. Hvis alle indgange i $A$ indeholdt 1 (dvs. $n=2^N-1$ før Inc$(A)$ udføres), så kopieres $A$ over i nyt array af dobbelt størrelse $2N$, hvor alle $A[i]=0$ bort set fra $A[N]=1$. Angiv en potentialefunktion kan man argumentere for at Inc tager amortiseret $O(1)$ tid. I nedenstående betegner $k$ antal $A[i]=1$, dvs. $k=|\{ i \mid A[i]=1\}|$.

En binær max-heap understøtter Insert og Heap-Extract-Max i worst-case $O(\log n)$ tid. Angiv en potentiale funktion så Insert tager amortiseret $O(\log n)$ tid og Heap-Extract-Max amortiseret $O(1)$ tid.