All Questions
15 questions
-1
votes
1
answer
246
views
Recurrence: T(n) = T(n/2) + T(n/4) + T(n/8) + Ω(n) , what is the complexity of T(n)?
how to solve the recurrence equation . T(n) = T(n/2) + T(n/4) + T(n/8) + Ω(n).
I can solve it if instead of Ω(n), we had (n), but now I can't solve it. please help me!
2
votes
1
answer
328
views
Calculating the Recurrence Relation T(n)=T(n / [(log n)^2]) + Θ(1)
I tried to solve this problem many hours and I think the solution is O(log n/[log (log n)^2]). but I'm not sure.Is this solution correct?
- 105
1
vote
1
answer
128
views
What is the complexity of an algorithm: T (n) = 3 * T (n ÷ b) + n² + 1?
What is the complexity of an algorithm: T (n) = 3 * T (n ÷ b) + n² + 1?
Ask a question
one
Can you help me know what is the complexity of: T (n) = 3 * T (n ÷ b) + n² + 1. When n> 1 ?.
I have been ...
- 13
2
votes
2
answers
3k
views
Solving recurrences with iteration, substitution, Master Theorem?
I'm familiar with solving recurrences with iteration:
t(1) = c1
t(2) = t(1) + c2 = c1 + c2
t(3) = t(2) + c2 = c1 + 2c2
...
t(n) = c1 + (n-1)c2 = O(n)
But what if I had a recurrence with no base case? ...
- 3,533
1
vote
2
answers
218
views
complexity algorithm recurrence relation
int function(int n){
if (n<=1)
return 1;
else
return (2*function(n/2));
}
What is the recurrence relation T(n) for running time , and why ?
- 13
3
votes
0
answers
2k
views
How to solve this recurrence relation: f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3 [closed]
f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3
I have attempted to solve it by letting
n = 2k
f(2k) = 3f(2k-1) - 2f(2k-2)
Then set
S(k) = f(2k)
S(k) = 3*S(k-1) - 2*S(k-2)
let S(k)...
- 160
0
votes
1
answer
545
views
Recurrence relations and asymptotic complexity
I am trying to understand the recurrence relation of f(n) = n^cos n and g(n) = n. I am told that this relation has no asymptotic behavior related to Big O, little o, Big Omega, little omega, or Theta. ...
- 57
1
vote
3
answers
228
views
Runtime of a loop that decays exponentially?
Where n is the input to the function can be any integer.
i = n, total = 0;
while (i > 0) {
for (j=0; j<i; j++)
for (k=0; k<i; k++)
total++;
i = i/4;
}
What is the ...
- 27
3
votes
2
answers
9k
views
Solving the recurrence T(n) = T(n/2) + T(n/4) + T(n/8)?
I'm trying to solve a recurrence T(n) = T(n/8) + T(n/2) + T(n/4).
I thought it would be a good idea to first try a recurrence tree method, and then use that as my guess for substitution method.
...
- 965
0
votes
2
answers
171
views
How many subproblems can this recurrence have while still being faster than an initial recurrence?
I'm having some trouble with an asymptotic analysis question :
My Question is to calculate maximum value if 'a' as stated in my question:
An Algorith A has running time T(n)= 7T(n/2) + n^2
and ...
- 281
2
votes
1
answer
181
views
Is my substitution solution to this recurrence correct?
I have a recurrence relation, it is like the following:
T(en) = 2(T(en-1)) + en, where e is the natural logarithm.
To solve this and find a Θ bound, i tried the following: I put k=en, and the ...
- 10.8k
-1
votes
2
answers
447
views
solving recurrence examples of form T(n-i) + f(n) [closed]
I've been working on a problem set for a bit now and I seem to have gotten the master method down for recurrence examples. However, I find myself having difficulties with other methods (recurrence ...
- 396
12
votes
2
answers
10k
views
When do floors and ceilings matter while solving recurrences?
I came across places where floors and ceilings are neglected while solving recurrences.
Example from CLRS (chapter 4, pg.83) where floor is neglected:
Here (pg.2, exercise 4.1–1) is an example where ...
- 6,169
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
1
vote
1
answer
233
views
recurrence solving [closed]
I need to find the complexity of the current recurrence:
T(n) = 1/(T(n-1) + 1) + 1
thanks in advance for any idea or link with useful information
- 7,903