Time/Space Complexity

Question 1

O(1)

Answer 1

Constant time. Most efficient algo

Question 2

Big O of pop/remove from hashmap

Answer 2

O(1)

Question 3

Big O of lookup in hashmap

Answer 3

O(1)

Question 4

Big O of search an array

Answer 4

Worse case: O(n)

Might have to go through entire array to find

Question 5

Big O of insert into hashmap

Answer 5

O(1)

Question 6

Big O of loop through an array

Answer 6

O(n)

Question 7

Big O of push/pop from array

Answer 7

O(1)

Question 8

What is O(log n)

Answer 8

Binary search.

On every iteration of loop, we halve the remaining elements and search again

Question 9

What is O(n^3)

Answer 9

3-D data structure. Get triplets of loops

Question 10

What is O(n * m)

Answer 10

2-D array that’s not a perfect square (ex. 2x3 grid)

Question 11

Big O of getting length of list

Answer 11

O(1)

Question 12

Big O deque vs. list

Answer 12

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)

Question 13

Big O of sum an array

Answer 13

O(n)

Question 14

What is O(n!)

Answer 14

Permutations
Ex. traveling salesman

Question 15

What is O(n log n)

Answer 15

Heap sort, merge sort

Question 16

What is O(2^n)

Answer 16

Recursion, with tree height of n and 2 branches.

Can be 4^n, 5^n, etc. Depends on how many loops for recursion

Question 17

Sort a list

Answer 17

O(n log n)

Question 18

What is O(n^2)

Answer 18

Traverse a square grid. Get every pair of elements in an array

Question 19

Big O of remove/insert from middle of array

Answer 19

Worse case: O(n) since values have to be moved around

Question 20

What is O(n)

Answer 20

Linear growth/time. As input grows, so does time

Question 21

Big O of lookup in array

Answer 21

O(1)

Question 22

Difference between O(n + m) and O(n * m)

Answer 22

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)

Question 23

When to add vs multiply for Big O setup

Answer 23

Add different complete instructions (loop through a, when done with all, loop through b)

Multiple if nested loop

Question 24

Big O of list extend()

Answer 24

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)

Question 25

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

Answer 25

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)

Question 26

Big O of python split()

Answer 26

Splitting a string into words can be considered an O(s) operation, since it needs to examine each character to determine where to split.

Question 27

Big O of max() on list

Answer 27

O(n)

Question 28

Big O of min() on list

Answer 28

O(n)

Question 29

Big O of remove() on list

Answer 29

O(n)

Question 30

Big O of extend() on list

Answer 30

O(k) where k is how many items are being added to the list

Question 31

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

Answer 31

O(n x m) O(n) for the 'i in range' part, and O(m) for extend(). Since it is nested, it is multiplied

Question 32

Big O of ' '.join(list)

Answer 32

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.

Question 33

Big O of using dict(zip(list1, list2))

Answer 33

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

Question 34

Big O of comparing two strings

Answer 34

Comparing two strings has a time complexity of O(k), where k is the length of the shorter string.

Question 35

Big O of comparing two lists of varying lenghts

Answer 35

The complexity of comparing two lists is O(n) if both lists have length n, and O(1) if the lists have different lengths

Question 36

Big O of comparing two lists that represent alphabet ([0] * 26)

Answer 36

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