Recent questions tagged recurrence-eqation - GATE Overflow

+1 vote

0 answers

1

Recurrence relation and probability
N rooms are there and they are numbered from 1 to N. A person P is in charge of room allocation and allocates these rooms inthe following way: Each query ask for two consecutive rooms. P selects two consecutive rooms out of the vacant ... selects (2,3) Seconds query onwards can not be processed. because although 1,4 are vacant, these rooms are not consecutive.

asked Aug 23, 2016 by dd Veteran (57k points) | 245 views

+3 votes

1 answer

2

time complexity to solve recurrence relation
recurrence relation for the functional value of F(n) is given below : $F(n) = a_{1}F(n-1) + a_{2}F(n-2) + a_{3}F(n-3) + ....... + a_{k}F(n-k)$ where $a_{i} =$ non zero constant. Best time complexity to compute F(n) ? assume k base values starting from F( ... ( $O(k_{2}r^{k_{1}n})$) B. Linear ( $O(n)$ ) C. Logarithmic ( $O(\log n)$ ) D. $O(n \log n)$

asked Aug 11, 2016 in Algorithms by dd Veteran (57k points) | 512 views

+2 votes

1 answer

3

Find the complexity of recurrence equation:
A scientist developed a new algorithm for computation and he observed that ot follows the recurrence equation as $T(n) = \begin{cases} 2T(n-1) -1 & \quad if\: n>0 \\ 1 & \quad otherwise \end{cases}$ What is the complexity of new algorithm? $2^n$ $2^{n+1}$ $2^{n-1}$ None of these

asked Jul 12, 2016 in Algorithms by sh!va Boss (32.5k points) | 211 views

+1 vote

2 answers

4

UGCNET-Dec2012-III-14
Let $T(n)$ be a function defined by $T(n) =1$ and $T(n)=2T (n/2) + \sqrt{n}$, which of the following is true? $T(n) = O(\sqrt{n})$ $T(n) = O(\log_2 n)$ $T(n) = O(n)$ $T(n) = O(n^2)$

asked Jul 12, 2016 in Algorithms by jothee Veteran (105k points) | 412 views

+2 votes

1 answer

5

Order and run time of the algorithm?
Running time of an algorithm T(n), where n is input size is given by T(n) = 8 T(n/2) + qn, if n>1 T(n) = p, if, n=1 where p and q are constants. The order of algorithm is A. n2 B. nn C. n3 D. n

asked Jan 22, 2016 in Algorithms by Purple Active (3k points) | 1.5k views

Page:

« prev
1
2
3

Recent questions tagged recurrence-eqation

50,644 questions

56,516 answers

195,578 comments

101,131 users