Time/Space Complexity Flashcards
O(1)
Constant time. Most efficient algo
Big O of pop/remove from hashmap
O(1)
Big O of lookup in hashmap
O(1)
Big O of search an array
Worse case: O(n)
Might have to go through entire array to find
Big O of insert into hashmap
O(1)
Big O of loop through an array
O(n)
Big O of push/pop from array
O(1)
What is O(log n)
Binary search.
On every iteration of loop, we halve the remaining elements and search again
What is O(n^3)
3-D data structure. Get triplets of loops
What is O(n * m)
2-D array that’s not a perfect square (ex. 2x3 grid)
Big O of getting length of list
O(1)
Big O deque vs. list
Index access:
- Deque: O(n)
- List: O(1)
Pop from right:
- Deque: O(1)
- List O(1)
Pop from left:
- Deque: O(1)
- List: O(n)
Big O of sum an array
O(n)
What is O(n!)
Permutations
Ex. traveling salesman
What is O(n log n)
Heap sort, merge sort
What is O(2^n)
Recursion, with tree height of n and 2 branches.
Can be 4^n, 5^n, etc. Depends on how many loops for recursion
Sort a list
O(n log n)
What is O(n^2)
Traverse a square grid. Get every pair of elements in an array
Big O of remove/insert from middle of array
Worse case: O(n) since values have to be moved around
What is O(n)
Linear growth/time. As input grows, so does time
Big O of lookup in array
O(1)
Difference between O(n + m) and O(n * m)
O(m+n) example:
for(int i = 0, i < m, i++)
//code
for(int j = 0, j < n, j++)
//code
m iterations of code happen. Then n iterations of code happens.
O(mn) example:
for(int i = 0, i < m, i++)
for(int j = 0, j < n, j++)
//code
For every iteration of m, we have n iterations of code. Imagine iterating over a non-square 2D array.
m and n do not necessarily equal the same value. If they did equal the same value, then for O(m+n):
O(m+n) => O(m+m) => O(2m) => O(m)
When to add vs multiply for Big O setup
Add different complete instructions (loop through a, when done with all, loop through b)
Multiple if nested loop
Big O of list extend()
The extend() operation here is O(k) where k=4 (the size of list2).
list1 = [1, 2, 3]
list2 = [4, 5, 6, 7]
list1.extend(list2)
Big O of:
class Solution:
def getConcatenation(self, nums: List[int]) -> List[int]:
result = []
for i in range(0, 2):
result.extend(nums)
return result
O(n)
range(0, 2) means we iterate twice, so O(2)
We extend the nums, which would be O(n), and we do it twice, so it would be O(2n)
We drop constants so final is O(n)
Big O of python split()
Splitting a string into words can be considered an O(s) operation, since it needs to examine each character to determine where to split.
Big O of max() on list
O(n)
Big O of min() on list
O(n)
Big O of remove() on list
O(n)
Big O of extend() on list
O(k) where k is how many items are being added to the list
Time complexity of:
class Solution:
def decompressRLElist(self, nums: List[int]) -> List[int]:
result = []
for i in range(0, len(nums), 2):
result.extend([nums[i + 1]] * nums[i])
return result
O(n x m)
O(n) for the ‘i in range’ part, and O(m) for extend(). Since it is nested, it is multiplied
Big O of ‘ ‘.join(list)
The time complexity of the join_string() function is O(n), where n is the total length of the input list of strings list_string, because the str. join() method iterates over each string in the list and concatenates them with a hyphen delimiter.
Big O of using dict(zip(list1, list2))
O(min(m,n))
When you use zip(list1, list2), it pairs up corresponding elements from the two lists until one of the lists runs out of elements. The time complexity of this operation is O(min(m,n)), where m is the length of list1 and n is the length of list2.
When converting the zipped pairs into a dictionary using dict(…), Python will iterate over the zipped pairs and insert each into the dictionary. Inserting an item into a dictionary is, on average, an O(1) operation. However, since this operation is done for each item, the overall time complexity becomes O(min(m,n)).
Big O of comparing two strings
Comparing two strings has a time complexity of O(k), where k is the length of the shorter string.
Big O of comparing two lists of varying lenghts
The complexity of comparing two lists is O(n) if both lists have length n, and O(1) if the lists have different lengths
Big O of comparing two lists that represent alphabet ([0] * 26)
These lists are always of the same length (both are of length 26, since they represent counts of the 26 lowercase English letters). So the complexity for comparing them would be O(26) which is a constant time and can be represented as O(1).
