retagged by
418 views
3 votes
3 votes

If $T$$\left ( 0 \right )$ $=$ $T$$\left ( 1 \right )$ $=$ $1$, each of the following recurrences for $n$ $\left ( \geq \right )$$2$ defines a function $T$ on the nonnegative integers. Which of the following CANNOT be bounded by a polynomial function?

where Floor$\left ( x \right )$ means $\rightarrow$ the greatest integer that is less than or equal to $x$.

  1. T$\left ( n \right )$ = $3T Floor$$\left ( n/2 \right )$ $+$$n$^$2$
  2. T$\left ( n \right )$ = $T$$\left ( n-1 \right )$$+$ $n$^$2$
  3. T$\left ( n \right )$= $T Floor$ $\left ( 7n/8 \right )$$+ 8n$ $+ 1$
  4. T$\left ( n \right )$ = $2T$$\left ( n-2 \right )$ $+ 1$
retagged by

1 Answer

2 votes
2 votes

ANS is D)

1.⊝(n^2),3.⊝(n)  by case III of master theorem.

2.⊝(n^3)  by solving recurrence.

4..⊝(2^n)  by solving recurrence.

Answer:

Related questions

1 votes
1 votes
1 answer
2
Bikram asked Jan 24, 2017
258 views
Which of the following sorting algorithms has the lowest best-case asymptotic algorithmic complexity?Selection sortMerge sortInsertion sortHeap sort