Efficiency/Number of Steps per Function Flashcards
1
Q
Linear Search
A
O(n)
2
Q
merge sort
A
O(nlogn)
3
Q
binary search
A
O(logn)
4
Q
no iteration
A
O(1)
5
Q
if 2 functions
A
the bigger one determines efficiency
6
Q
monkey puzzle
A
O(n!)
7
Q
Traveling salesperson
A
O(n!)
8
Q
Map coloring
A
O(3**n)
9
Q
Satisfiability
A
O(2**n)
10
Q
Towers of Hanoii
A
steps = (2**number of disks)-1
11
Q
Insertion Sort
A
O(n**2)
12
Q
Binary Search Tree formula for number of nodes given k levels
A
n = 2**k - 1
