Array

In this section of the course, we'll consider various data-structures and understand how different operations on them can be analyzed for complexity. We'll also digress into general discussions around trade-offs of space and time, so as to cultivate the readers' thought process for reasoning about complexity.

We'll start with the most basic data-structure - the Array. Almost all languages allow users to create arrays. Insert or retrieval operations on an array are well-known to be constant or O(1) operations. But what makes these operations constant time operations?

Contiguous memory allocation is the key to an array's constant time retrieval/insert of an element given the index. Any language platform that you code in would request the underlying operating system to allocate a contiguous block of memory for an array. Suppose the following is a block of memory allocated by the operating system for an array of 10 elements in computer memory.