The Stack Overflow podcast is back! Listen to an interview with our new CEO.

New answers tagged

1

The second implementation is correct (so Theorem 2.2 survives): If the condition $c(v) > c(u)$ causes the inner while to halt, that same value of $v$ will be give the optimal value for every following value of $g$, simply because the condition is independent of $g$.


1

Dividing both sides by $n$ then introducing $S(m):=\frac{T(2^n)}{2^n}$ yields: $$S(m)=S(m/2)+1+\frac{1}{m}$$ It follows that: $$1<S(m)-S(m/2)\leq 2$$ And further: $$\forall k, 1<S(m/2^k)-S(m/2^{k+1})\leq 2$$ Now summing for $k=1\dots \log(m)-1$ gives us: $$S(m)=\Theta(\log(m))$$ And so: $$T(n)=\Theta(n\cdot\log\log n)$$


1

Using master theorem you can say it is $\Theta(n\log n)$. Also, try to expand the relation: $$T(n) = 3(3T(\frac{n}{3^2}) + \frac{n}{3}) + n = 3^2 T(\frac{n}{3^2}) + 2n$$ If you continue the above expansion, you will get that $T(n) \sim n\log_3(n) = \Theta(n\log(n))$.


2

Here's the relevant part of the proof, quoting verbatim: First, show that $\phi(\phi(n)) < n/2$. This can be done as such: Let $n = \prod_{i=1}^rp_i^{k_i}$ be the prime factorisation of $n$ ($p_i$ prime, $k_i>0$) Suppose $n$ is even. Then $\phi(n) = n\prod_{i=1}^r(1-\frac{1}{p_i}) \leq n(1-\frac{1}{2}) \leq n/2.$ Thus $\phi(\phi(n)) &...


2

First, you can get the the result from the second xase of master theorem. Second, you have a mistake in your exapnsion: $$T(n) = 2T(\frac{n}{2}) + n\log(n) = 2(2T(\frac{n}{2^2} + \frac{n}{2}\log(\frac{n}{2})) + n\log(n) = n\log(n) + n\log(\frac{n}{2}) + 2^2T(\frac{n}{2^2}) = n\log(n) + n\log(\frac{n}{2}) + 2^2(2T(\frac{n}{2^3} + \frac{n}{2^2}\log(\frac{n}{...


2

Try to solve the recurrent by expanding equality case: $$T(n) = T(2n/3) + \Theta(1) = T(2^2n/3^3) + \Theta(1) + \Theta(1)$$ Now you can see $T(n) = \Theta(\log_{\frac{3}{2}}(n))$. Because each time $\Theta(1)$ is added up to reach to the leaf of the expnasion tree. Also, you can reach this result using the master theorem.


0

$n^2 \cdot \sqrt{n} = n^{5/2}$, then you can proceed with the Master Theorem as normal. If you specifically need to use the Recursion Tree Method for solving recurrences, then you can still proceed normally. Root Level : $n^{5/2}$ Next Level : $4 \cdot (n\ /\ 2)^{5/2} = 2^{4/2} \cdot n^{5/2}\ /\ 2^{5/2} = n^{5/2}\ /\ 2^{1/2}$ Next Level : $16 \cdot (n\ /\ ...


2

diplodoc explained in the comments one way to solve the recursion. Your recursion is $$ A_n = 1 + \frac{A_0 + \cdots + A_{n-1}}{n+1}, \quad A_0 = 1. $$ The trick is to calculate $$ (n+1)A_n - n A_{n-1} = (n+1 + A_0 + \cdots + A_{n-1}) - (n + A_0 + \cdots + A_{n-2}) = 1 + A_{n-1}, $$ and so $A_n = A_{n-1} + 1/(n+1)$. From here it follows easily that $A_n$ is ...


Top 50 recent answers are included