4. You are given that algorithm A has a computational time-complexity of: p(m) = 0(q(m)) in which m is a variable; here we can take m to represent the number of

features. You will consider the following exact time complexities (each part represents a different algorithm): (i) p(m) = 3m (ii) p(m) = 100m (iii) p(m) = 8m³ (iv) p(m) 10 log₂ (m) (v) p(m) = 2m (a) For each time complexity given above, give the simplest-form asymptotic tight bound, e(q(m)). We measure the computation time with m = m3 features, and get a time of T3. We want to know the computation time T4 of running the same algorithm with m4 = Rm3 features, for R > 1, as well as an asymptotic bound for it. We can consider m3 to be constant, and R to be the variable that is increasing. For each time-complexity function p(m) given above, we have T₁_p(m₂) _p(Rm3) T₂ p(m₂) p(m₂) (b) Give the exact for each of the time complexities p(m) given above, in terms of R. Express in simplest form. (Simplest form will generally include R, but will not include m4; and will only include m3 if necessary.) (c) Now for each result of (b), give a simplest-form asymptotic tight bound in terms of R. Your answers should be in the form (q (R)), in which q'(R) is your asymptotic tight- bound expression. Your expression may include m3 if necessary, but not m4. Compare your answers to (c) with your answers to (a); what conclusions can you draw? Compare your answers to (c) with your answers to (b) (that is, compare exact of (b) with the asymptotic-bound function q'(R) of (c)). What conclusions can you draw? T₂ (d) (e)