All Questions
26 questions
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
0
votes
1
answer
776
views
T(n) = T(n - sqrt(n)) + T(sqrt(n)) + 1
How to solve this recurrence?
Is Induction the only way to get the answer? If so, how would you guess the base case?
My guess was O(logn) but I'm not sure how to solve it.
- 2,465
0
votes
1
answer
96
views
Time Complexity Of The Below Program
algorithm what (n)
begin
if n = 1 then call A
else
begin
what (n-1);
call B(n)
end
end.
In the above program, I was asked to find the time ...
- 511
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
0
votes
1
answer
79
views
What's the recurrence relation of the following algorithm?
Is the recurrence relation below T(n) = T(n-1) + 2 + T(n+1) ?
I'm just counting the mid variable assignment and the last line, since all the if statements are excluding the other ones ... is this ...
- 59
1
vote
2
answers
3k
views
How to get the time complexity of this recurrence: T(n) = sqrt(n) * T(sqrt(n)) + n
This recurrence:
T(n) = sqrt(n) * T(sqrt(n)) + n
It does not appear to be solvable with Master theorem. It also does not appear to be solvable with Akra-Bazzi. Even if I set n = 2^k so that T(2^k) = ...
- 2,074
-3
votes
2
answers
8k
views
Solving recurrence T(n) = T(n/2) + 2T(n/4) + n?
I am studying about recurrences using my friend's pdf (Algorithms Unlocked) and trying to solve the problems about recurrences and it is not yet clear to me about the mechanics of the recursion tree(I ...
- 25
-1
votes
1
answer
621
views
Determining the running time for recurrence relation T(n) = T(n-1)+n
How do I determine the running time (in terms of Big-Theta) for the algorithm of input size n that satisfies recurrence relation T(n) = T(n-1)+n where n >= 1 and with initial condition T(1) = 1?
...
- 217
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
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
2
votes
2
answers
164
views
How to do asymptotic analysis on this weird recurrence?
I came across this weird recurrence equation:
T(n,h) = T(n/2, h1) + T(n/2, h-h1) + nh
and:
T(1,h) = O(h)
I need to find the asymptotic upper bound. I have never come across a recurrence relation ...
- 1,239
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
3
answers
659
views
Find theta of: T(n) = T(n^(1/2)) + 1
I tried this for many hours and I keep arriving at log(logn) (where log is base 2) but this does not agree with Masters Theorem which maintains it would be just log(n).
- 41
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