search
Log In
0 votes
0 answers
1
0 votes
1 answer
2
Use the substitution method to prove that the recurrence $T(n)=T(n-1) + \Theta(n)$ has the solution $T(n) =\Theta(n^2)$.
asked Jun 27, 2019 in Algorithms akash.dinkar12 55 views
0 votes
1 answer
3
Use mathematical induction to show that when $n$ is an exact power of $2$, the solution of the recurrence $T(n) = \begin{cases} 2 \text{, if n=2, } \\2T(n/2)+n \text{, if n=$2^k$,for k >1} \end{cases}$ is $T(n) = n\ lg\ n$.
asked Jun 26, 2019 in Algorithms akash.dinkar12 108 views
1 vote
1 answer
4
The solution of $\sqrt{a_n} – 2\sqrt{a_{n-1}} + \sqrt{a_{n-2}} = 0$ where $a_0 = 1$ and $a_1 = 2$ is ${\Big[\frac{2^{n+1} + (-1)^n}{3}\Big]}^2$ $(n+1)^2$ $(n-1)^3$ $(n-1)^2$
asked Jun 5, 2019 in Combinatory `JEET 196 views
2 votes
1 answer
5
Consider the following algorithms. Assume, procedure $A$ and procedure $B$ take $O(1)$ and $O(1/n)$ unit of time respectively. Derive the time complexity of the algorithm in $O$ -notation. algorithm what (n) begin if n = 1 then call A else begin what (n-1); call B(n) end ... $c$ So complexity should be $O(1)$. But answer is $O(n)$.What I am doing wrong?
asked Jun 4, 2019 in Algorithms kshitij 226 views
1 vote
1 answer
6
What will be solution of recurrence relation if roots are like this: r1=-2, r2=2, r3=-2, r4=2 is this the case of repetitive roots?
asked May 14, 2019 in Combinatory aditi19 121 views
0 votes
0 answers
7
What is the general form of the particular solution guaranteed to exist of the linear nonhomogeneous recurrence relation $a_n$=$6a_{n-1}$-$12a_{n-2}$+$8a_{n-3}$+F(n) if F(n)=$n^2$ F(n)=$2^n$ F(n)=$n2^n$ F(n)=$(-2)^n$ F(n)=$n^22^n$ F(n)=$n^3(-2)^n$ F(n)=3
asked May 14, 2019 in Combinatory aditi19 149 views
0 votes
0 answers
8
2 votes
1 answer
9
You can climb up a staircase of $n$ stairs by taking steps of one or two stairs at a time. Formulate a recurrence relation for counting $a_n$, the number of distinct ways in which you can climb up the staircase. Mention the boundary conditions for your recurrence relation. Find a closed form expression for $a_n$ by solving your recurrence.
asked May 12, 2019 in Algorithms akash.dinkar12 197 views
0 votes
1 answer
10
How many bit sequences of length seven contain an even number of 0s? I'm trying to solve this using recurrence relation Is my approach correct? Let T(n) be the string having even number of 0s T(1)=1 {1} T(2)=2 {00, 11} T(3)=4 {001, 010, 100, 111} Case 1-we add 1 to strings of length ... =T(n-1) Case 2-we add 0 to strings of length n-1 having odd number of 0s T(n)=T(n-1) Hence, we have T(n)=2T(n-1)
asked Apr 29, 2019 in Combinatory aditi19 163 views
0 votes
2 answers
11
0 votes
0 answers
12
Is this the correct way to solve ? Q) int algorithm(int n) { int sum =0;k,j; for (k=0;k<n/2;k++) for(j=0;j<10;j++) sum++; return 4*algorithm(n/2)*algorithm(n/2)+algorithm(n/2)*algorithm(n/2) }
asked Mar 15, 2019 in Algorithms syncronizing 264 views
0 votes
1 answer
13
What is the time complexity of the following recurrence relation and step to derive the same $T(n) = T(\sqrt{n}) + log(logn)$
asked Jan 20, 2019 in Algorithms VikramRB 360 views
0 votes
0 answers
14
A two dimensional array is stored in column major form in memory if the elements are stored in the following sequence ... can be calculated as the column number of the element we are looking for summing with the $row \times column$ number of elements. How does the above recurrence relation work?
asked Jan 7, 2019 in DS kauray 181 views
0 votes
1 answer
15
T(n) = T(n/4) + T(3n/4) + n How to solve these type of problems? Can I solve this using master theorm by considering X = T(3N/4) +N THEN T(N) = T(N/4) +X CAN WE SOLVE LIKE THIS? PLEASE HELP
asked Jan 4, 2019 in Algorithms Mayankprakash 330 views
7 votes
1 answer
18
Consider the following piece of pseudo-code: A(n){ if(n==0) return 1; return A(√n) + B(n) + C(n) + D(n); } B(n){ if (n==0) return n; return B(n-1); } C(n){ return A (√n); } D(n){ return n; } What is the time complexity in terms of Big $\Theta$ notation for the function call to procedure A? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n \log \log n)$ $\Theta(n^2 \log n)$
asked Dec 27, 2018 in Algorithms Ruturaj Mohanty 416 views
0 votes
1 answer
19
1 vote
0 answers
20
1 vote
2 answers
21
recurrence relation 2a$_{n}=a_{n-1}+2^{n}$ intial condtion a$_{0}$=1 value of a$_{100}$
asked Dec 12, 2018 in Combinatory amit166 84 views
0 votes
0 answers
22
Difference between getting closed form of generating function and closed form of the given sequence ,pls someone explain with an example
asked Dec 10, 2018 in Combinatory codingo1234 76 views
1 vote
1 answer
23
int A(int n){ for(i = 1; i < n; i++) for(j = 1; j < i; j *= 2) for(k = j; k >= 1; k /= 2) if(n = 0) return 1; else{ for(z = 0; z < n; z++){ // do something } } } How do find the complexity of this problem? The answer is supposed to be O(n log log n), but it maybe wrong.
asked Nov 22, 2018 in Algorithms gmrishikumar 1.1k views
3 votes
2 answers
24
T(n) = sqrt(n) * T(sqrt(n)) + n Given solution is O(log log n). But my solution is O(n log log n). 'wolframalpha'' shows the answer same as mine. You can find the solution here. Can anyone confirm the solution and provide an explantion?
asked Nov 22, 2018 in Algorithms gmrishikumar 2.3k views
...