Recent questions tagged recurrence-relation

which formula to use in master theorm

Give asymptotic upper and lower bound for $T(n)$ given below. Assume $T(n)$ is constant for $n \leq 2$. $T(n) = 4T( \sqrt{n} ) + \lg^2n$$T(n) = \theta (\lg ( \lg ^2 n) \l...

Consider the following statements:The running time of dynamic programming algorithm is always $\theta(\rho)$ where $\rho$ is number of subproblemsWhen a recurrence relati...

The recurrence relation $T(n)=7T(n/7)+n$ has the solution:$O(n)$$O(logn)$$O(nlog(n))$$O(n^2)$

Consider the algorithm that solves problems of size $n$ by recursively solving two sub problems of size $n-1$ and then combining the solutions in constant time. Then the ...

Which of the following is correct recurrence for worst case of QuickSort?$T(n)=T(n-4)+T(n-2)+O(1)$$T(n)=T(n-1)+T(0)+O(n)$$T(n)=2T(n/2)+O(n)$$T(n)=4T(n/2)+O(n)$

Solve the recurrence relation for the number of rounds in the tournament described in question $14.$

How many rounds are in the elimination tournament described in question $14$ when there are $32$ teams?

Suppose that there are $n = 2^{k}$ teams in an elimination tournament, where there are $\frac{n}{2}$ games in the first round, with the $\frac{n}{2} = 2^{k-1}$ winners pl...

Give a big-O estimate for the function $f$ given below if $f$ is an increasing function.$f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$

Find $f (n)$ when $n = 3k,$ where $f$ satisfies the recurrence relation $f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$

Give a big-O estimate for the function $f$ in question $10$ if $f$ is an increasing function.

Find $f (n)$ when $n = 2^{k},$ where $f$ satisfies the recurrence relation $f (n) = f (n/2) + 1 \:\text{with}\: f (1) = 1.$

Suppose that $f (n) = f (n/5) + 3n^{2}$ when $n$ is a positive integer divisible by $5, \:\text{and}\: f (1) = 4.$ Find$f (5)$$f (125)$$f (3125)$

Suppose that $f (n) = 2f (n/2) + 3$ when $n$ is an even positive integer, and $f (1) = 5.$ Find$f (2)$$f (8)$$f (64)$$(1024)$

Suppose that $f (n) = f (n/3) + 1$ when $n$ is a positive integer divisible by $3,$ and $f (1) = 1.$ Find$f (3)$$f (27)$$f (729)$

Express the fast multiplication algorithm in pseudocode.