1
Q
give the linear search complexities
A
worst O(n) best O(1) average O(n) space O(1)
2
Q
give the binary search complexities
A
worst O(log n) best O(1) average O(log n) space O(1)
3
Q
define big O
A
f(n) is O(g(n))
if there exists n_0 >= 1, c > 0 such that
f(n) <= cg(n)
for every n >= n_0
4
Q
give the complexities from worst to best
A
n^n n^2 n log n n log n 1
