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
Given a hash table/dictionary with n = dict.length, what is the time complexity to add or remove key-value pair
O(1)
Given a hash table/dictionary with n = dict.length, what is the time complexity check if a key exists
O(1)
Given a hash table/dictionary with n = dict.length, what is the time complexity check if a value exists
O(n)
Given a hash table/dictionary with n = dict.length, what is the time complexity to access or modify a value associated with a key
O(1)
Given a hash table/dictionary with n = dict.length, what is the time complexity iterate over all of the keys, values, or both
O(n)
Given a set with n = set.length, what is the time complexity to add or remove an element
O(1)
Given a set with n = set.length, what is the time complexity to check if an element exists
O(1)
Given a stack with n = stack.length, what is the time complexity to push an element
If implemented with a dynamic array
O(1)
Given a stack with n = stack.length, what is the time complexity to pop and element
If implemented with a dynamic array
O(1)
Given a stack with n = stack.length, what is the time complexity to peek (see an element at the top of the stack)
If implemented with a dynamic array
O(1)
Given a stack with n = stack.length, what is the time complexity to access or modify an element at an arbitrary index
If implemented with a dynamic array
O(1)
Given a stack with n = stack.length, what is the time complexity to check if an element exists
If implemented with a dynamic array
O(n)
Given a queue with n = queue.length, what is the time complexity to enqueue an element
If implemented with a doubly linked list
O(1)
Given a queue with n = queue.length, what is the time complexity to dequeue an element
If implemented with a doubly linked list
O(1)
Given a queue with n = queue.length, what is the time complexity to peek (see the element at the front of the queue)
If implemented with a doubly linked list
O(1)
Given a queue with n = queue.length, what is the time complexity to access or modify an element at an arbitrary index
If implemented with a doubly linked list
O(n)
Given a queue with n = queue.length, what is the time complexity to check if an element exists
If implemented with a doubly linked list
O(n)
Given a binary search tree with n as the number of nodes in the tree, what is the time complexity to add or remove an element
Average and worst case
The average case is when the tree is well balanced - each depth is close to full. The worst case is when the tree is just a straight line.
O(n) worst case, O(log n) average case
Given a binary search tree with n as the number of nodes in the tree, what is the time complexity to check if an element exists
Average and worst case
The average case is when the tree is well balanced - each depth is close to full. The worst case is when the tree is just a straight line.
O(n) worst case, O(log n) average case
Given a heap/priority queue with n = heap.length, and talking about min heaps, what is the time complexity to add an element
O(log n)
Given a heap/priority queue with n = heap.length, and talking about min heaps, what is the time complexity to delete the minimum element
O(log n)
Given a heap/priority queue with n = heap.length, and talking about min heaps, what is the time complexity to find the minimum element
O(1)
Given a heap/priority queue with n = heap.length, and talking about min heaps, what is the time complexity to check if an element exists
O(n)
What is time complexity of the worst case search in a binary search where your search space is of size n
O(log n)
What is the time complexity of sort where n is the size of data being sorted
O(n · log n)
What is the time complexity of a depth first search (DFS) and breadth first search (BFS) on a graph
O(n⋅k+e), where n is the number of nodes, e is the number of edges, if each node is handled in O(1) other than iterating over edges
What is the space complexity of a depth first search (DFS) and breadth first search (BFS) on a graph
typically O(n), but if it’s in a graph, might be O(n+e) to store the graph
What is the time complexity of dynamic programming
O(n⋅k), where n is the number of states and k is the work done at each state
What is the space complexity of dynamic programming
O(n), where n is the number of states
What are advantages and disadvantages of a linked list compared to an array
Advantages:
- Add or remove an element at O(1) compared to O(n) compared to an array
- Linked lists do not have a fixed size
Disadvantages:
- There is no random access; you must traverse the linked list to access the nth element
- Linked lists have more overhead than arrays; space for the value, next, and prev, pointers
