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

1
Q

Given an array with n = arr.length, what is the time complexity to add or remove element at the end of the array

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Given an array with n = arr.length, what is the time complexity to add or remove element from arbitrary index

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Given an array with n = arr.length, what is the time complexity to access or modify an element at arbitrary index

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Given an array with n = arr.length, what is the time complexity to check if element exists

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Given an array with n = arr.length, what is the time complexity for the two pointers algorithm

A

O(n⋅k), where k is the work done at each iteration, includes sliding window

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Given an array with n = arr.length, what is the time complexity to build a prefix sum

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Given an array with n = arr.length, what is the time complexity to find the sum of a subarray given a prefix sum

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Given a string with n = s.length, what is the time complexity to add or remove character

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Given a string with n = s.length, what is the time complexity to access element at arbitrary index

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Given a string with n = s.length, what is the time complexity to concatenate two strings

A

O(n+m), where m is the length of the other string

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Given a string with n = s.length, what is the time complexity to create a substring

A

O(m), where m is the length of the substring

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Given a string with n = s.length, what is the time complexity to for the two pointers algorithm

A

O(n⋅k), where k is the work done at each iteration, includes sliding window

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Given a string with n = s.length, what is the time complexity to building a string from joining an array, stringbuilder, etc.

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Given a linked list with n nodes, what is the time complexity to add or remove element given pointer before add/removal location

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Given a linked list with n nodes, what is the time complexity to add or remove element given pointer at the add/removal location

A

O(1) if doubly linked

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Given a linked list with n nodes, what is the time complexity to add or remove element at arbitrary position without pointer

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Given a linked list with n nodes, what is the time complexity to access element at arbitrary position without pointer

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Given a linked list with n nodes, what is the time complexity to check if element exists

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Given a linked list with n nodes, what is the time complexity to reverse between position i and j

A

O(j−i)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Given a linked list with n nodes what is the time complexity to detect a cycle

A

O(n) using fast-slow pointers or hash map

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Given a hash table/dictionary with n = dict.length, what is the time complexity to add or remove key-value pair

22
Q

Given a hash table/dictionary with n = dict.length, what is the time complexity check if a key exists

23
Q

Given a hash table/dictionary with n = dict.length, what is the time complexity check if a value exists

24
Q

Given a hash table/dictionary with n = dict.length, what is the time complexity to access or modify a value associated with a key

25
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)*
26
Given a **set** with `n = set.length`, what is the time complexity to add or remove an element
*O(1)*
27
Given a **set** with `n = set.length`, what is the time complexity to check if an element exists
*O(1)*
28
Given a **stack** with `n = stack.length`, what is the time complexity to push an element | If implemented with a dynamic array
*O(1)*
29
Given a **stack** with `n = stack.length`, what is the time complexity to pop and element | If implemented with a dynamic array
*O(1)*
30
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)*
31
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)*
32
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)*
33
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)*
34
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)*
35
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)*
36
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)*
37
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)*
38
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 ## Footnote 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
39
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 ## Footnote 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
40
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)*
41
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)*
42
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)*
43
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)*
44
What is time complexity of the worst case search in a **binary search** where your search space is of size `n`
*O(log n)*
45
What is the time complexity of **sort** where `n` is the size of data being sorted
*O(n · log n)*
46
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
47
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
48
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
49
What is the space complexity of **dynamic programming**
*O(n)*, where *n* is the number of states
50
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