All Questions
17 questions
0
votes
0
answers
46
views
Same asymptotic growth - Master Theorem
Given the master theorem:
if a) f(1) = g(1) and b) f(n) = a f(n/b) + g(n),
then:
(1) f(n) ∈ Θ(n^c); if a < b^c
(2) f(n) ∈ Θ(n^c * log n); if a = b^c
(3) f(n) ∈ Θ(n ^ log b (a); if a > ...
- 41
0
votes
0
answers
88
views
Complexity for Recursive Function (Big O Notation)
I know how to find the complexity of a basic recursive function such as a factorial function, but I don't know how to get started on how to do something a little more complicated like this. What would ...
- 151
8
votes
2
answers
477
views
How to solve the following recurrence?
I am not familiar with recurrence-solving techniques outside of the master theorem, recursion trees, and the substitution method. I am guessing that solving the following recurrence for a big-O bound ...
- 81
1
vote
3
answers
1k
views
Cost of a java method with multiple recursion
We have the following Java method:
static void comb(int[] a, int i, int max) {
if(i < 0) {
for(int h = 0; h < a.length; h++)
System.out.print((char)(’a’+a[h]));
...
- 59
0
votes
1
answer
270
views
Find Recurrence Relation from Code Snippet
I know some basic rules to create Recurrence Relation from code like this;
if n=0 return 1
else return F(n-1)*n
The Recurrence Relation of this code is F(n)=F(n-1)*n for n>0 But I have a more ...
- 2,441
15
votes
3
answers
2k
views
Calculating the Recurrence Relation T(n)=T(n / log n) + Θ(1)
The question comes from Introduction to Algorithms 3rd Edition, P63, Problem 3-6, where it's introduced as Iterated functions. I rewrite it as follows:
int T(int n){
for(int count = 0; n > 2 ; ...
- 163
4
votes
2
answers
337
views
Analyzing time complexity using recurrence relations
Complexity analysis noob here.
I'm trying to figure out the time complexity of a recursive algorithm using the given recurrence relation below -
T(n) = n + 4T(n/2)
There are three methods for this ...
- 1,200
0
votes
1
answer
1k
views
Big O Notation analysis using recursion tree
A problem from: http://qpleple.com/divide-and-conquer/
Comparison of algorithms
You are product manager at Facebook and three engineers from your team come up with these three algorithms to detect ...
- 4,290
0
votes
1
answer
363
views
Solving recurrence equation by substituion
I am trying to solve T(n) = sqrt(n)*T(sqrt(n))+sqrt(n) by drawing a reccurence tree and solving it be the substitution method. But I am having a hard time wrapping my head around how the sqrt method ...
- 739
4
votes
4
answers
38k
views
Calculating the Recurrence Relation T(n)=T(n-1)+logn
We are to solve the recurrence relation through repeating substitution:
T(n)=T(n-1)+logn
I started the substitution and got the following.
T(n)=T(n-2)+log(n)+log(n-1)
By logarithm product rule, log(...
- 357
3
votes
2
answers
10k
views
How to solve the recursive complexity T(n) = T(n/4)+T(3n/4)+cn
I am solving this recurrence using a recursion tree. The total cost of each level is n, and the depth of the tree is between log (n) base 4 and log (n) base 4/3. Intuitively, I expect the solution to ...
- 57
0
votes
1
answer
443
views
Space Complexity Recurrence
So this is a 2 part question.
I have some code that asks for the time complexity, and it consists of 3 for loops (nested):
public void use_space(int n)
for(int i=0;i<N;i++)
for(int j=0;j&...
0
votes
1
answer
112
views
Calculating time complexity when number of elements is not given in algorithm
I want to find the data at i'th position from end in a linked list. I have written this code using recursion :
NODE STRUCTURE :
struct Node
{
int data;
struct Node * next;
}
CODE :
int i = 10;...
- 4,868
0
votes
1
answer
978
views
CLSR chip testing problem
Finding ONE good VLSI chip in a population of good and bad ones, by using the
pair test.
Chip A Chip B Conclusion
------- ------- ----------
B is ...
- 105
8
votes
1
answer
53k
views
Solving the recurrence relation T(n) = √n T(√n) + n [closed]
Is it possible to solve the recurrence relation
T(n) = √n T(√n) + n
Using the Master Theorem? It is not of the form
T(n) = a ⋅ T(n / b) + f(n)
but this problem is given in the exercise of ...
- 105