Multiple choices 16/50
(Choose 1 answer)
A. (iii)
B. (i)
C. (ii)
D. (iv)
Next
E. None of the other choices is correct.
MASTER THEOREM Let ƒ be an increasing function that satisfies the recurrence relation
f(n) = af (n/b) + cnd
whenever n = b, where k is a positive integer, a 1, b is an integer greater than 1, and c and d are real numbers with c positive and d nonnegative. Then
O(nd)if a < bd,
f(n) is O(nd log n) if a = bd,
O(nlogs") if a b².
Use the Master Theorem to give the best big-O estimate for the function f,where satisfies the recurrence relation
f(n)=3f(n/3) + 4n
and fis an increasing function.
(i) O(n)
(ii) O(n²)
(iii) O(nlogn)
(iv) O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 17
18
19 20
21
22
23
24
25
26 27
28
29
30
31
32
33
34
35
36 37
38 39 40 41
42
43
44
45
46
47
48
49 50
