# Tag Info

## Hot answers tagged recurrence-relation

• 4,410

### 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

• 270k
Accepted

• 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

• 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