asymptotic analysis

Question 1

asymptotic notation big oh

Answer 1

𝑂≈≤
0 <= f(n) <= cg(n)
asymptotic upper bound

Question 2

asymptotic notation big omega, Ω

Answer 2

Ω≈≥
cg(n) <= f(n)
asymptotic lower bound

Question 3

Asymptotic Notation – Theta, Θ

Answer 3

Θ≈=
0 c1g(n)<= f(n) <= c2g(n)
asymptotic tight bound

Question 4

selection sort pseudocode

Answer 4

Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted

Question 5

asymptotic dominance rating

Answer 5

𝑛!≫2^𝑛≫𝑛^3≫𝑛^2≫𝑛 log⁡𝑛≫𝑛≫log⁡𝑛≫1

Question 6

logarithms

Answer 6

Saying 𝑏^𝑥=𝑦 is equivalent to saying that 𝑥=log_𝑏⁡𝑦.

Question 7

binary search time complexity

Answer 7

log n