Recent questions tagged recurrence-relation

Consider the following function:function X(n,r) { if(r==0 or n == r) then return 1; else return (X(n-1,r-1,) + X(n-1,r)); }Find the worst case time complexity of function...

$T\left ( n \right )= 8T\left ( \frac{n}{2} \right )+\left ( n\cdot logn \right )^{2.99}$Also can $\mathcal{O}(n^{3})$ be an upper bound to above recurrence relation?

Let $$T(n)=\sqrt{n} \cdot T(\sqrt{n})+n$$What will be asymptotic bound on $T(n) ?$$\Theta(\sqrt{n} \log n)$$\Theta(\log \log n)$$\Theta(n \log \log n)$$\Theta(\sqrt{n} \l...

Solve the following recurrences using recursion tree method and write the asymptotic time complexity T(n)=T(n/2)+n^2

What is the solution to the following recurrence?\[T(n)=\left\{\begin{array}{ll}1 & \text { if } n \leq 10, \\\sqrt{n} \cdot T(\sqrt{n})+n & \text { if } n>10.\end{array}...

The Lucas sequence $L_{n}$ is defined by the recurrence relation:\[L_{n}=L_{n-1}+L_{n-2}, \quad \text { for } \quad n \geq 3,\]with $L_{1}=1$ and $L_{2}=3$.Which one of t...

What is the recurrence relation for the ternary strings of length $n$ which can be constructed using 0,1 or 2 only such that the number of 0’s and number of 1's is odd ...