13
votes
Can we solve a "very" exponential recurrence?
It depends what you mean by "solve". This is tetration, and it has a number of "closed" forms. For example:
$$\begin{eqnarray*}T_0 & = & 1 \\ T_{n+1} & = & 2^{T_n}\...
- 19.1k
5
votes
Accepted
Solve $T (n) = T (\frac n2) + n(2 - \cos n)$
Since $|\cos n| \leq 1$, we have $1 \leq 2-\cos n \leq 3$, and so $$ T(n) = T(n/2) + \Theta(n). $$ This is something that the master theorem can handle.
- 270k
5
votes
Accepted
Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n
You are right: you can apply the Akra-Bazzi method to find that $T(n) \in \Theta(n)$.
Your professor is right: since $\Theta(n) \subseteq \mathcal{O}(n\log n)$, it is also true that $T(n) \in \mathcal{...
- 7,193
4
votes
Solve $T (n) = T (\frac n2) + n(2 - \cos n)$
$n(2-\cos n)$ always lies between $n$ and $3n$.
On expansion, we get:
$T(n) \leq 3 (n+n/2+n/4+\dotsc+1) \leq 6n$
and
$T(n) \geq (n+n/2+n/4+\dotsc+1) \geq n$
Hence, $T(n) = \Theta(n)$.
- 3,976
4
votes
Accepted
Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails
The problem in the question is a good example for two related principles.
Thanks to the substitution method in your try 2, you have found $c=b=1$ will enable the induction step for $T(n)\le cn-b$ to ...
- 34.7k
3
votes
Solve $T (n) = T (\frac n2) + n(2 - \cos n)$
Define $T^-(n) = T^-(n/2) + n$ and $T^+(n) = T^+(n/2) + 3n$.
You can see that $T^-(n) \le T(n) \le T^+(n)$.
Since the master theorem applies to both $T^-(n)$ and $T^+(n)$ which have solution $\Theta(n)...
- 23.9k
3
votes
Accepted
simple but (seemingly?) tricky recurrence
We shall asymptotically solve $\color{blue}{ f(2n) = f(n)·\log(f(n))·2^c }$ for any $c∈ℝ$ as $n → ∞$ (where $\log = \log_2$).
$
\def\lfrac#1#2{{\large\frac{#1}{#2}}}
$
~ ~ ~
Note that $\log\log(2n) = \...
- 707
3
votes
Recurrence $T(n) = T(n-1) + (-1)^nn$, $T(0) = 1$
Here are the first few values of the expression $\sum_{k=1}^n (-1)^k k$, starting with $n = 1$:
$$ -1, 1, -2, 2, -3, 3, -4, 4, -5, 5,\ldots$$
Hopefully you can spot the pattern.
- 270k
3
votes
Solving $T(n) = 2T(\lfloor{\frac{n}{2}}\rfloor) + n$ with substitution method
If we multiply the left-hand side $T(\lfloor n/2 \rfloor)$ by $2$, we get $2T(\lfloor n/2 \rfloor)$, not $T(n)$.
Let $P(n)$ be a propositional function. To prove that $P(n)$ is true for all $n \ge 1$, ...
- 1,100
3
votes
Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails
Your second idea is good, there is no need to start at $n = 1$:
You already proved that for $n\geqslant 3$, $T(n) \leqslant n - 1$.
You can now say that since $n-1 \leqslant n$ and since $T(1)\...
- 7,193
3
votes
Formal mathematical resolution for Recurrence Relations
Formaly, for all $n>N$,
$$T(n-1)+c_0n\le T(n)\le T(n-1)+c_1n$$
If we expand the right inequality,
$$T(n)\le T(n-1)+c_1n\le T(n-2)+c_1n+c_1(n-1)\le\cdots \le T(N)+c_1\sum_{i={N+1}}^ni\\
=T(N)+c_1\...
- 4,410
2
votes
Recurrence and Time complexity
Let $S(m) = \log_2 (2T(2^m))$. Then $S(m)$ satisfies the recurrence
$$
S(m) = 2S(m-1), \quad S(0) = 3.
$$
You can work it out from here.
- 270k
2
votes
How to solve $T(n) = 27T(n/9) + n^3$ with substitution method
I am assuming that the recurrence relation you are trying to solve is:
$$T(n) = 27T(n /9) + n^3$$
Using the substitution method, you can prove that for any $k \leqslant \log_3 n$:
$$T(n) = 3^{3k}T\...
- 7,193
2
votes
Accepted
Finding time complexity $T(n) = 2^n T(n/2) + n^n$
We prove by induction that $T(n) \leq Cn^n$, where $C = \max(T(2),4/3)$. The base cases are clear. For the inductive case,
$$
T(n) = 2^nT(n/2) + n^n \leq C2^n (n/2)^{n/2} + n^n = C\left(\frac{2}{n}\...
- 270k
2
votes
Accepted
Solve $T(n) = 3T(\frac n3 + 5) +\frac n2$
Define $S(n) = T(n+\alpha)$ for some $\alpha$ to be chosen later. Then:
$$
S(n)=3T\left(\frac{n}{3} + \frac{\alpha}{3}+5\right)+\frac{n+\alpha}{3} = 3S\left(\frac{n}{3} - \frac{2\alpha}{3}+5\right) +\...
- 23.9k
2
votes
Programmatically determine if a tie is possible in US elections
Just create a bit array of say 600 entries, initially with bit 0 set. This array represents the possible number of votes from the first n state, for n = 0 initially.
Take the first state. If it has ...
- 25.4k
2
votes
Recursive function - proof by induction
I think it's a template match, meaning if you have some list $L = [x_1, x_2, \dots, x_n]$, then $L = x:L'$ where $L' = [x_2, x_3, \dots, x_n]$.
So you can imagine what that definition is saying is ...
- 342
2
votes
Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n
Let $n=2^m$. The recurrence is written
$$T(2^m)=2T(2^{m-3})+2T(2^{m-2})+2^m$$
or
$$U(m)=2U(m-3)+2U(m-2)+2^m.$$
A particular solution is given by $U=c2^m$ and more precisely
$$c=2\frac c8+2\frac c4+1,$$...
- 4,410
2
votes
A recursive relation for the number of well formed nested parentheses of length $n$ and depth $\leq d$
Suppose that $w$ is a well-formed parenthetical word of depth at most $d$. Then either $w = \epsilon$, or $d > 0$ and $w = (x)y$, where $x$ is a parenthetical word of depth at most $d-1$, and $y$ ...
- 270k
2
votes
Accepted
Formal mathematical resolution for Recurrence Relations
Let me make the following suggestion: get rid of asymptotic notation.
Here is how to do that. Your recurrence relation is really the following:
$$
T(n) = \begin{cases}
1 & \text{if } n = 1, \\
T(n-...
- 270k
1
vote
Recurrence relation with O(loglogn)
If $m:=\lg\lg n$, then $\lg\lg\sqrt n=m-1$. With $T(n)=T(2^{2^m})=:S(m)$, your recurrence becomes
$$S(m)=S(m-1)+O(m),$$ which has an $O(m^2)$ solution, and $$T(n)=O(\lg^2\lg n).$$
The result holds ...
- 4,410
1
vote
Solve the recurrence equation $T\left(n\right)=\sqrt{n}\cdot T\left(\sqrt{n}\right)+c\log n$
Using the nice trick of @Cesareo, and setting $n=2^{2^m}$,
$$\frac{T(2^{2^m})}{2^{2^m}}=\frac{T\left(\sqrt{2^{2^m}}\right)}{\sqrt{2^{2^m}}}+\frac{c\log2^{2^m}}{2^{2^m}}$$
is of the form
$$S(m)=S(m-1)+...
- 4,410
1
vote
Solve the recurrence equation $T\left(n\right)=\sqrt{n}\cdot T\left(\sqrt{n}\right)+c\log n$
For $n > 0$ we have
$$
\frac{T(n)}{n} = \frac{T(\sqrt{n})}{\sqrt{n}}+c\frac{\ln n}{n}
$$
calling $R(n) = \frac{T(n)}{n}$ we follow with
$$
R(n) = R(\sqrt{n})+c\frac{\ln n}{n}
$$
but now
$$
R\left(2^...
- 121
1
vote
Accepted
Skyline problem with triangular buildings
If holes are ignored (only the outline is computed), this is an instance of computing a single face of arrangement of half-lines (rays).
With half-lines, the maximum number of vertices in a single ...
- 1,396
1
vote
Accepted
Solve recurrence where the base case's time complexity is a function of the original input size
You are right that in order to analyze the recurrence, you need to take two parameters into account: the original list size $N$, and the size of the sublist currently operated on $n$. In terms of ...
- 270k
1
vote
Regularity condition for cases 1 & 2
First, let's discuss the meaning of the regularity condition. It states that $af(n/b)<=cf(n)$ for a constant $c < 1$ and $n > n_0$. Now consider the recurrence equation $T(n) = aT(n/b) + f(n)$...
- 4,017
1
vote
Regularity condition for cases 1 & 2
Can there be a situation where $f(n)=\Omega(n^{\log_b a + \varepsilon})$ is true but the regularity condition does not hold?
Yes. Let $f(n)$ be equal to $n$ if $n$ is between an even power of two ...
- 23.9k
1
vote
Why is the time complexity of merge sort with a $\Theta(n^2)$ merge function $\Theta(n^2)$?
Because the work done is
$$ T(n) = 2T(n/2) + n^2 \leq
\sum_{i=0}^{\log_2 n} 2^i \left(\frac{n}{2^i}\right)^2 =
n^2 \sum_{i=0}^{\log_2 n} \frac{2^i}{2^{2i}} = O(n^2).
$$
Try for yourself to see what ...
- 13.3k
1
vote
Accepted
Given a source and destination, find the path with minimum stress level in a Graph
I don't think your algorithm is correct, but keep in mind that I haven't read your code carefully; consider replacing the code with pseudocode.
One solution that could work in $O(m \log m)$ time is to ...
- 13.3k
1
vote
How to solve $T(n) = 2T(n/4) + n \log n$ with substitution method?
Use complete induction. The base case is obvious, and here is the induction step:
$$T(n)=\\2T\left(\frac{n}{4}\right)+n\log(n)\le\\ 2c\cdot\frac{n}{4}\log\left(\frac{n}{4}\right)+n\log(n)\le\\\frac{2c}...
- 10.8k
Only top scored, non community-wiki answers of a minimum length are eligible