All Questions
Tagged with recursive-algorithms asymptotics
62
questions
1
vote
1
answer
24
views
Does my proof that the recurrence $T(n) = T(\frac{n}{2}) + d = \Theta(lgn)$work?
Suppose we have the recurrence
$T(n) = T(\frac{n}{2}) + d$ if $n = 2^j$ and where is some integer greater than $0$ (i.e n is even). I know that this recurrence is $\Theta(lg(n))$, and I want to prove ...
- 496
1
vote
1
answer
99
views
Big-O analysis of recurrence relation
I'm not sure if I should be posting this question here or under Stackoverflow, but given that it's algorithmic analysis, I figured Math was the right call. I have 2
functions that I'm trying to find ...
- 29
0
votes
1
answer
45
views
Asymptotic Bound [closed]
$$T(n) = \Theta \left ( n^{1/2} \left ( 1 + \int_1^n \frac{1}{u^{3/2}}\ du \right ) \right ) = \Theta \left ( n^{1/2} \right )$$
This asymptotic bound is evaluated to be $n^{1/2}$ but isn't the ...
- 23
2
votes
1
answer
122
views
Asymptotic analysis of recursion with Big O
I am trying to perform asymptotic analysis on the following function in terms of Big O:
$T(n) = T(n^{\frac{1}{2}}) + n$
$T(1) = 1$
I have found that: $T(n) = T(1) + \sum_{k = 1}^{log(log(n)) -1} n^{\...
- 327
1
vote
0
answers
201
views
Generalized Master Theorem (Divide-and-Conquer) using Ceil / Floor
I'm a bit tired of virtually all books deriving the master theorem always using their own variation: They sometimes use inequalities $T(n)< T(\frac{n}{b})+f(n)$, sometimes are more sloppy and use $\...
- 342
0
votes
2
answers
263
views
How can I find an asymptotic solution to this recurrence?
How can I find an asymptotic solution to the recurrence
$$T(n) = 4T(n/4) + 2T(n/2) + C$$
I replaced the $4T(n/4)$ with $4T(n/2)$ and used the master theorem to get an upper bound of $O(n^{\log_2 6})$ ...
- 411
1
vote
1
answer
236
views
finding a constant runtime algorithm to calculate a recursive summation
Suppose we have a sequence of integers $A_n$ where $A_0$, ..., $A_{k=1}$ < $50$, and for each subsequent term in the sequence, $A_i = A_{i-1}b_1 + A_{i-2}b_2 +... + A_{i-k}b_k$. ($A_0$ through $A_{...
- 4,581
0
votes
1
answer
2k
views
How to solve $T(n) = 5T(\frac{n}{2}) + n^3 \log n$ using master method?
I'm trying to solve the recurrence $T(n) = 5T(\frac{n}{2}) + n^3 \log n$ using master method.
$$
a = 5, b = 2
$$
$$
n^{\log_b a} = n^{\log_2 5} = n^{2.32} \in Θ(n^{2.32})
$$
How can I continue? ...
- 11
2
votes
2
answers
143
views
How to simplify the summation of a recurrence relation
After solving the recurrence relation
$$T(n) = 3T(\frac{n}{3}) + n\log(n)$$
I get following equation
$$T(n)=3kT(\frac{n}{3k})+ n\log(n) + n\log(\frac{n}{3}) + n\log(\frac{n}{3^2})+\dots+n\log(\frac{n}{...
- 21
0
votes
1
answer
568
views
Apply master theorem work for binary search with linear operation at each level
I'm working on the problem from the Introduction to Algorithms book, where there is the following recurrence relation $T(n) = T(\frac{n}{2}) + \Theta(N)$, where $N$ is the size of the array we are ...
- 533
5
votes
2
answers
92
views
Suppose each $x_{n+1} \le \left(\sum_{i=1}^n x_i \right)^{-c}$ for some $c \in (0,1)$. How quickly can $\sum_{i=1}^n x_i $ grow?
Suppose we have a sequence $x_1,x_2,\ldots \in [0,1]$ that satisfies $x_{n+1} \le \left(\sum_{i=1}^n x_i \right)^{-c}$ for each $n$ and some $c \in (0,1)$. The relation comes from deciding stepsizes ...
- 10.4k
-1
votes
1
answer
4k
views
Solving the recurrence $T(n) = 3T(n/4) + n\log n , T(1) = 1$ [closed]
Solve the recurrence $T(n) = 3T(n/4) + n\log n , T(1) = 1$
Can someone help me to solve this recurrence using substitution method?
0
votes
1
answer
30
views
Exact number of steps in a recursion [closed]
I am studying algorithms and I came across this problem:
$t(1) = 1$ and $t(n) = 4t(n/2) + n^2$
Calculate the exact value of $t(n)$ for all $n=2^l, l \in N $
Initially I thought this would be a ...
0
votes
1
answer
46
views
What is the difference between $O(n + \log n)$ and $O(n + n/2)$?
I've learned that when we see O(log n) we consider that a given problem is halve every time. So having O(n + log n) would be that we first iterate n times once and then the problem is continually ...
- 428
1
vote
2
answers
301
views
Algorithm runnning time $T(n) = \sqrt{n} \cdot T(\sqrt{n}) + \sqrt{n} $ using substitution
I need to solve the following recurrence, only using the substituion method (CLRS):
$$ T(n) = \sqrt n \cdot T(\sqrt n) + \sqrt n $$
This is what I have done so far:
Changing variables
$$ m = \log_{...
- 19