Register

NIELIT Scientist B 2020 November: 100

• recategorized by
1,171 views
1 votes
1 votes

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 running time of the algorithm would be:

  1. $O(n)$
  2. $O(\log n)$
  3. $O(n\log n)$
  4. $O(n^2)$
• recategorized by
User Avatar

1 Answer

1 votes
1 votes
recurrence relation :

T(n)=2.T(n-1)+c , n>0

T(n)=1, n=0.

as per back substitution method,

T(n) = 2$^k$.T(n-k)+ 2$^{k-1}$c+....+2$^0$c

T(n) = 2$^n$.T(0)+ 2$^{k-1}$c+....+2$^0$c

T(n) =  2$^{n+1}$-1

T(n) =  O(2$^n$)
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

3 votes
3 votes
4 answers
1
gatecse asked Dec 9, 2020
1,380 views
NIELIT Scientist B 2020 November: 21
There are $6$ boxes numbered $1, 2, \dots\dots,6$. Each box is to be filled up either with a red or a green ball in such a way that at least $1$ box contains a green ball and the boxes containing green balls are consecutively numbered. The total number of ways in which this can be done is : $18$ $19$ $20$ $21$
There are $6$ boxes numbered $1, 2, \dots\dots,6$. Each box is to be filled up either with a red or a green ball in such a way that at least $1$ box contains a green ball...
User Avatar
2 votes
2 votes
2 answers
2
gatecse asked Dec 9, 2020
730 views
NIELIT Scientist B 2020 November: 22
Number of letter repeated in the given word $’MEASUREMENTS’$ are indicated in front of each alternative. Identify the correct alternative. $M_2E_2A_2S_2U_1R_1N_1T_1$ $M_2E_3A_1S_1U_2R_1N_2T_1$ $M_2E_2A_1S_2U_1R_1N_1T_1$ $M_2E_3A_1S_2U_1R_1N_1T_1$
Number of letter repeated in the given word $’MEASUREMENTS’$ are indicated in front of each alternative. Identify the correct alternative.$M_2E_2A_2S_2U_1R_1N_1T_1$$M...
User Avatar
2 votes
2 votes
1 answer
3
gatecse asked Dec 9, 2020
712 views
NIELIT Scientist B 2020 November: 23
If $09/12/2001(DD/MM/YYYY)$ happens to be Sunday, then $09/12/1971$ would have been a: Wednesday Tuesday Saturday Thursday
If $09/12/2001(DD/MM/YYYY)$ happens to be Sunday, then $09/12/1971$ would have been a:WednesdayTuesdaySaturdayThursday
User Avatar
2 votes
2 votes
2 answers
4
gatecse asked Dec 9, 2020
778 views
NIELIT Scientist B 2020 November: 24
If a cube with length, height and width equal to $10\; cm$, is reduced to a smaller cube of height, length and width of $9\; cm$ then reduction in volume is : $172\;cm^3$ $729 \;cm^3$ $271\;cm^3$ None of the options
If a cube with length, height and width equal to $10\; cm$, is reduced to a smaller cube of height, length and width of $9\; cm$ then reduction in volume is :$172\;cm^3$$...
User Avatar
Link Copied!