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.

Block of memory allocated by the operating system.

Suppose the array we requested above is for integers. The next part to the puzzle is the size of the type for which we requested the array. The type refers to the data type the array holds, it could be integers, characters or even objects. In the case of Java, an integer is 4 bytes so let's go with that. Realize that if given the starting address of the array in the computer memory, it is trivial to compute the starting memory address of any element in the array given the index of the element.

As an example, say the starting address of the array for the below snippet of code is 25.

 // initialize array of 10 elements.
 // The variable myArray points to memory address 25
 int[] myArray = new int[10]

The variable myArray literally points to 25 in the computer’s memory. We also know each integer is 4 bytes in size. The first integer would lie at address 25, the second integer would lie at 25 + (1 * 4) = 29, the third integer would lie at 25 + (2 * 4) = 33. To find out where the nth element of the ...