Use a visual proof to demonstrate that the better strategy for resizing arrays is doubling the size to make it easier for students to understand.

This proof uses amortised analysis to show that doubling the size of the array is more efficient than increasing the size of the array by a constant amount.

To see the visual proof, check out Don Blaheta's paper, "A Visual Proof of Amortised-linear Resizable Arrays".

Note from the CS Teaching Tips Team: for more information about amortised analysis, visit the Amortised Analysis Wikipedia page.

Tags

External Source

“A Visual Proof of Amortised-linear Resizable Arrays” by Don Blaheta

Other Tips By

Other Tips By Don Blaheta