#16 algorithm analysis

Question 1

upper bound

Answer 1

big-O represent the upper bound of the number of operations performed in an algorithm

Question 2

big-O formal definition

Answer 2

T(n) is O(f(n)) if some constant C > 0 and n(sub zero) >= 1, cx f(n) >= T(n) everywhere that n>= n(sub zero)

Question 3

asymptotic complexity

smallest to largest

Answer 3

O(1) constant
O(log(n)) logarithmic
O(n) linear
O(n log(n)) n log n
O(n^2) quadratic
O(n^3) cubic
O(n^k) polynomial
O(k^n) exponential
O(n!) factorial
O(n^n) n to the n

Question 4

critical section

Answer 4

executed the most, the operation is central to the algorithm, in deeply nested for loops