Big 0 Time

Question 1

Linear Time

Answer 1

O(n)

Question 2

Constant Time

Answer 2

O(1)

Question 3

Quadratic Time

Answer 3

O(n^2)

Question 4

What scenario do we care about when measuring time complexity?

Answer 4

Worst case scenario/upper bound

Question 5

Logarithmic Time

Answer 5

O(logn)

Question 6

Traveling Salesman Time Complexity

Answer 6

O(n!)

Question 7

Bubble Sort Time Complexity

Answer 7

O(n^2)

Question 8

Insertion Sort Time Complexity

Answer 8

O(n^2)

Question 9

Merge Sort Time Complexity

Answer 9

O(nlogn)

Question 10

Quicksort Time Complexity

Answer 10

O(nlogn)

Question 11

Binary Search Time Complexity

Answer 11

O(logn)

Question 12

First Recurring Character in a string Time Complexity

Answer 12

O(n^2)

Question 13

Rank the algorithms Rate of Increase for Big O

Answer 13

O(logn)>O(n)>O(nlogn)>O(n^2)>O(2^n)>O(n!)

Question 14

When there is a function with multiple calls, the runtime will often be:

Answer 14

O(branches^depth)

Question 15

Binary Tree Insert/find

Answer 15

O(logn)

Question 16

Hash Table

Answer 16

constant time O(1)

Question 17

Linked List

Answer 17

O(n)

Question 18

Objects

Answer 18

Constant time for lookup/insert/removal, linear time for searching O(n)

Question 19

Arrays

Answer 19

Access O(1), Searching O(n), Insertion/Removal depends on beginning or end

Question 20

Binary Heap

Answer 20

Insert/Remove O(logn)

Question 21

Graph: Adjacency Matrix vs List Edge Tradeoffs

Answer 21

List:

• Takes up less Space
• Faster iteration over edges
• Slower to query edge

Matrix:

• Takes up more space (in sparse graphs)
• Longer to iterate over edges
• Faster to query an edge