Time Complexity Flashcards
Time complexity (Big O) of * Arrays * Strings * Linked Lists * Hash Table/Dictionary * Set * Stack * Queue * Binary Search Tree * Heap/Priority Queue * Binary Search * Miscellaneous
Given an array with n = arr.length, what is the time complexity to add or remove element at the end of the array
O(1) amortized
It’s amortized O(1), not O(1).
Let’s say the list reserved size is 8 elements and it doubles in size when space runs out. You want to push 50 elements.
The first 8 elements push in O(1). The nineth triggers reallocation and 8 copies, followed by an O(1) push. The next 7 push in O(1). The seventeenth triggers reallocation and 16 copies, followed by an O(1) push. The next 15 push in O(1). The thirty-third triggers reallocation and 32 copies, followed by an O(1) push. The next 31 push in O(1). This continues as the size of list is doubled again at pushing the 65th, 129th, 257th element, etc..
So all of the pushes have O(1) complexity, we had 64 copies at O(1), and 3 reallocations at O(n), with n = 8, 16, and 32. Note that this is a geometric series and asymptotically equals O(n) with n = the final size of the list. That means the whole operation of pushing n objects onto the list is O(n). If we amortize that per element, it’s O(n)/n = O(1).
Given an array with n = arr.length, what is the time complexity to add or remove element from arbitrary index
O(n)
Given an array with n = arr.length, what is the time complexity to access or modify an element at arbitrary index
O(1)
Given an array with n = arr.length, what is the time complexity to check if element exists
O(n)
Given an array with n = arr.length, what is the time complexity for the two pointers algorithm
O(n⋅k), where k is the work done at each iteration, includes sliding window
Given an array with n = arr.length, what is the time complexity to build a prefix sum
O(n)
Given an array with n = arr.length, what is the time complexity to find the sum of a subarray given a prefix sum
O(1)
Given a string with n = s.length, what is the time complexity to add or remove character
O(n)
Given a string with n = s.length, what is the time complexity to access element at arbitrary index
O(1)
Given a string with n = s.length, what is the time complexity to concatenate two strings
O(n+m), where m is the length of the other string
Given a string with n = s.length, what is the time complexity to create a substring
O(m), where m is the length of the substring
Given a string with n = s.length, what is the time complexity to for the two pointers algorithm
O(n⋅k), where k is the work done at each iteration, includes sliding window
Given a string with n = s.length, what is the time complexity to building a string from joining an array, stringbuilder, etc.
O(n)
Given a linked list with n nodes, what is the time complexity to add or remove element given pointer before add/removal location
O(1)
Given a linked list with n nodes, what is the time complexity to add or remove element given pointer at the add/removal location
O(1) if doubly linked
Given a linked list with n nodes, what is the time complexity to add or remove element at arbitrary position without pointer
O(n)
Given a linked list with n nodes, what is the time complexity to access element at arbitrary position without pointer
O(n)
Given a linked list with n nodes, what is the time complexity to check if element exists
O(n)
Given a linked list with n nodes, what is the time complexity to reverse between position i and j
O(j−i)
Given a linked list with n nodes what is the time complexity to detect a cycle
O(n) using fast-slow pointers or hash map
