Complexity

Question 1

give the linear search complexities

Answer 1

worst O(n)
best O(1)
average O(n)
space O(1)

Question 2

give the binary search complexities

Answer 2

worst O(log n)
best O(1)
average O(log n)
space O(1)

Question 3

define big O

Answer 3

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

Question 4

give the complexities from worst to best

Answer 4

n^n
n^2
n log n
n
log n
1