Algorithm

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...

Written by Vortana Say · 1 min read

 

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)