# Big O of Common Array Operations Array:  an array is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key. (wikipedia)

Knowing Big O of these operations will help analyze complexity of algorithm.

• Access
• Space complexity = O(1)
• We don’t use any extra space to access the array
• Time complexity = O(1)
• Let’s say we have array nums = [1, 2, 3, 4]
• To access value 4 we can do a basic operation nums. The same for large array
• Set
• Space complexity = O(1)
• We don’t use any extra space to access the array
• Time complexity = O(1)
• Let’s say we have array nums = [1, 2, 3, 4]
• To access value in index 0, we can do a basic operation nums = 10. The same for large array
• Traverse or Search
• Space complexity = O(1)
• We don’t use any extra space to access the array; we just moving through array
• Time complexity = O(n)
• Let’s say we have array nums = [1, 2, 3, 4]
• We move or search through the whole array. In worse case, it will be the same as number of element in nums
• Copy
• Space complexity = O(n)
• We need to create a new array with the new memory slots that the space need. In the worse case, it needs n slots
• Time complexity = O(n)
• We have to traverse and copy element to another array
• Insert: all three operations have space complexity O(1)
• at the beginning
• static array: in kotlin Array()
• Time complexity: O(n)
• dynamic array: in kotlin ArrayList()
• Time complexity: O(n)
• at the end
• static array: in kotlin Array()
• Time complexity: O(n)
• dynamic array: in kotlin ArrayList()
• Time complexity: O(1) – It’s actually amortized (average). The system will allocate extra space when needed
• somewhere between beginning and the end
• static array: in kotlin Array()
• Time complexity: O(n) – We need to shift the element
• dynamic array: in kotlin ArrayList()
• Time complexity: O(n) – We need to shift the element
• Remove: all three operations have space complexity O(1)
• at the beginning
• Time complexity: O(n) – If we remove the first element, we need to remove the element and reindexing the array. Example: [1,2,3] -> [2,3] index 0 is now 2
• at the end
• Time complexity: O(1) – no need to reindexing the array
• somewhere between beginning and the end
• Time complexity: O(n) – we have to shift the elements and reindexing

Recap:

Operation Time Complexity Space Complexity
Access O(1) O(1)
Set O(1) O(1)
Traverse or Search O(n) O(1)
Copy O(n) O(n)
Insert

• At the beginning
• At the end
• somewhere between beginning and the end

• O(n)
• O(1)
• O(n)

• O(1)
• O(1)
• O(1)
Insert

• At the beginning
• At the end
• somewhere between beginning and the end

• O(n)
• O(1)
• O(n)

• O(1)
• O(1)
• O(1)  ## Sorted Squared Array

in  