Recent questions tagged recurrence-eqation - GATE Overflow

+3 votes

1 answer

1

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 | 611 views

+2 votes

1 answer

2

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 | 229 views

+1 vote

3 answers

3

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 | 505 views

+2 votes

1 answer

4

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 | 1.7k views

Page:

« prev
1
2
3

Recent questions tagged recurrence-eqation

52,345 questions

60,513 answers

201,931 comments

95,355 users