Arrays

Question 1

Time complexity to access an element in array?

Answer 1

O(1)

Question 2

Time complexity to search in array/list?

Answer 2

O(n)

Question 3

Time complexity of search in a sorted array?

Answer 3

O(log(n))

Question 4

Time complexity to Insert an item in array/list?

Answer 4

O(n) - Insertion, in the middle of an array, would require shifting all the subsequent elements to the right by one and that takes O(n)

Question 5

Time complexity to insert an element at the end of an array/list?

Answer 5

O(1)

Question 6

Time complexity to remove an element from the middle of an array/list?

Answer 6

O(n) - Removal would require shifting all the subsequent elements to the left by one and that takes O(n)

Question 7

Time complexity to remove an element from the end of an array/list?

Answer 7

O(1) - Special case of removal where no other element needs to be shifted.

Question 8

Advantages of Arrays

Answer 8

1. Storing multiply elements of the same kind w/ one single variable name
2. Accessing elements if fast if you have the index
3. Arrays are better at processing many values easily and quickly
4. Sorting and searching the values is easier in arrays

Question 9

Disadvantages of Arrays

Answer 9

1. Addition/removal of elements to/from the middle of the array is slow because the remaining elements need to be shifted to accomodate new/missing elements (An exception to this is if the position to be inserted/removed is at the end of the array.)
2. Depending on the language, arrays are fixed in size. it cannot alter its size after initialization. If an insertion causes the total number of elements to exceed the size, a new array has to be allocated and the existing elements have to be copied over. The act of creating a new array and transferring elements over takes O(n) time.

Question 10

What is a Subarray?

Answer 10

A range of contiguous values within an array.

Example: given an array [2, 3, 6, 1, 5, 4], [3, 6, 1] is a subarray while [3, 1, 5] is not a subarray.

Question 11

What is a Subsequence?

Answer 11

A sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements.

Example: given an array [2, 3, 6, 1, 5, 4], [3, 1, 5] is a subsequence but [3, 5, 1] is not a subsequence.

Question 12

What is an Array?

Answer 12

Arrays hold values of the same type at contiguous memory locations. In an array, we’re usually concerned about two things - the position/index of an element and the element itself