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[3]. 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[0] = 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)