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}\...
user avatar
  • 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.
user avatar
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{...
user avatar
  • 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)$.
user avatar
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 ...
user avatar
  • 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)...
user avatar
  • 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) = \...
user avatar
  • 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.
user avatar
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$, ...
user avatar
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)\...
user avatar
  • 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\...
user avatar
  • 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.
user avatar
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\...
user avatar
  • 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}\...
user avatar
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) +\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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,$$...
user avatar
  • 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$ ...
user avatar
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-...
user avatar
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 ...
user avatar
  • 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)+...
user avatar
  • 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^...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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)$...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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}...
user avatar
  • 10.8k

Only top scored, non community-wiki answers of a minimum length are eligible