Give the tightest asymptotic bounds you can for the followin

Give the tightest asymptotic bounds you can for the following recurrences^(1) and provide a short explanation of your solution. T(n) = T(n - 1) + n^11. T(n) = 3 T(n/2) + n^2 T(n) = 14 T(n/3) + n^2 T(n) = 12 T(n/11) + n log n. T(n) = 4 T(n/2) + n^2 squreroot n. T(n) = n(T(n/2)^2). T(n) = T(n-1) + 14 Ig n. T(n) = (log n) T(n/2) + 1.

Solution

a.)

The tightest upper bound for the given recurrence relation will be o(n¹²), because when we solve this recurrence relation we will end up with an arithmetic series. which wil be like 1¹¹+2¹¹+3¹¹+.......+(n-1)¹¹+n¹¹

the result of which will be o(n¹²)

b.)

When we solve this recurrence relation using master theorem the solution will fall into case 3 because b=2 and a =3 so n^log_ba=n < n², So T(n) = o(n²)

c.)

When we solve the given recurence relation using master theorem the comparison between n^log_ba and f(n) will fall into case 1 of the theorem, So the time complexity will be O(n³). or we can write o(n³) for tightest upper bound.

d.)

When we compare the n^log_ba and f(n) for the given recurrence relation using master theorem then this will fall into case 3 of master theorem since n log n > n So T(n) = O(f(n)) = O(n log n). The relation is same for tightest upper bound as well o(n log n).