Question

1. Estimate the asymptotics of the following recurrence relations. You may use the master theorem. \text { (a) } T(n)=3 T(n / 3)+O(n) \text { (b) } T(n)=8 T(n / 2)+O\left(n^{2}\right) \text { (c) } T(n)=T(n / 3)+O(\sqrt{n}) \text { (d) } T(n)=2 T(n / 4)+O(\sqrt{n})

Fig: 1

Fig: 2

Fig: 3

Fig: 4

Fig: 5