4

Suppose that $f(n) = O(n^{\log_b a - \epsilon})$. According to the definition, there exist constants $N,C>0$ such that $f(n) \leq Cn^{\log_b a - \epsilon}$ for all $n \geq N$. Let $M$ be the maximum value of $f(n)/n^{\log_b a - \epsilon}$ over all positive integers $n < N$. The maximum exists since there are only finitely many such $n$. Then $f(n) \leq ...


2

The definition of $\lceil x \rceil$ is: $\lceil x \rceil$ is the minimal integer $n$ such that $n \geq x$. (The existence of such an integer makes the reals an Archimedean field.) Let us assume, for the sake of contradiction, that $\lceil x \rceil \geq x + 1$. Then $\lceil x \rceil - 1 \geq x$. Since $\lceil x \rceil - 1$ is also an integer, this ...


2

Let $S(n) = T(2^n)$. Write a recurrence formula for S, solve S(n), use that to solve T(n).


2

Ignoring floors (see, e.g., the paragraph "Ignoring Floors and Ceilings Is Okay, Honest" in Chapter 1 of Algorithms for a discussion), your recurrence is of the form $$ T(n) = aT(n/b) + f(n), $$ with $a=b=3$ and $f(n) = 2 n \log n$. You can then immediately apply the master theorem since, for $k=1$, $f(n) \in \Theta(n^{\log_b a} \log^k n) = \Theta(...


2

Usually the general form of the recurrences solved by the Master theorem is stated as: $$ T(n) = aT\left(\frac{n}{b}\right) + f(n). $$ In your recurrence you have $a=2$, $b=\frac{8}{5}$, and $f(n)=1$.


2

The recurrence in question is $T(n) = aT(n/b) + f(n)$. Suppose that $n = b^k$, and the leaves are at $n = 1$. The root $b^k$ has $a$ children labelled $b^{k-1}$ (the label is the size of the subproblem). Each one of them has $a$ children labelled $b^{k-2}$, and in total there are $a^2$ children at depth $2$ labelled $b^{k-2}$. More generally, there are $a^\...


2

Case 3 does not apply. Indeed: $$ f(n) = n \log n \not\in \Omega(n^{\log_9 10}) = \Omega(n^{\log_b a}). $$ However case $1$ applies since, for $0<c \le 0.01$ $$ f(n) = n \log n \in O(n^{1.04 - 0.01}) \subset O(n^{\log_9 10 - 0.01} ) \subseteq O(n^{\log_b a - c} ). $$ This shows that $T(n) \in \Theta(n^{\log_9 10})$.


2

When $f(n)$ is said to be polynomially smaller than $g(n)$ it just means that there is some constant $\varepsilon > 0$ such that $f(n) \in O(g(n) n^{-\varepsilon})$. This is not about being able to bound $f(n)$ from above and/or below but about the growth rate of $f(n)$ when compared to $g(n)$. In other words you want $\frac{g(n)}{f(n)}$ to grow at least ...


2

If you are just interested in an upper bound you can notice that $T(n) \le S(n)$ where $S(n) = 3 S(n/3) + \frac{n}{2}$ and has solution $S(n) = O(n \log n)$. Alternatively there is always induction. You can show that, for $n \ge 2$, $T(n) \le c n \log n$. For $2 \le n < 7$, $T(n)$ is a constant and $n \log n \ge 1$. Therefore the claim is true for a ...


2

The division by 3 makes the task a little non-trivial, but you can still figure out how to proceed in the manner proposed by the answer suggested by Nathaniel in the comments. Let $n = 3^{2^k-2}$ and you can modify the recurrence equation as $$T(n) = 4T\left(\frac{\sqrt{n}}{3}\right) + (\log_3{2})^2.(\log_3n)^2$$ However, this modification will only bring a ...


1

Akra and Bazzi proved a generalization of the master theorem which, in particular, implies that the formulas in the master theorem remain true even if you're adding some "noise" of the form you consider. In fact, the Akra–Bazzi theorem can handle noise of magnitude $O\bigl(\frac{n}{\log^2 n}\bigr)$.


1

$n^{\log_6 8} = n^c$ for some $c>1$ (you can tell that $\log_6 8 > 1$ from the fact that $8>6$). Then $n^c = \omega(n \log n)$. Indeed: $$\lim_{n \to +\infty} \frac{n^c}{n \log n} = \lim_{n \to +\infty} \frac{n^{c-1}}{\log n} = \lim_{n \to +\infty} \frac{(c-1)n^{c-2}}{1/n} = \lim_{n \to +\infty} (c-1)n^{c-1} = +\infty.$$


1

We know that $n! \le n^n$, therefore $\log n! \le n \log n$. Then $$ T(n) \le 99T( \frac{n}{100} ) + n \log n $$ Let $c=\log_{100} 99 < 1$ and notice that $n \log n$ is polynomially larger than $n^c$. Indeed: $n \log n \in \Omega(n) \subset \Omega(n^c).$ By the master theorem we have $T(n) = O(n \log n)$. This is tight because $\Omega(n \log n)$ is also a ...


1

Your guess works: if $T(n) \le c n^3$ and $c \ge 2$ then $$ T(n) = 4c \frac{n^3}{8} + n^3 = \frac{c}{2} n^3 + n^3 = cn^3 \left(\frac{1}{2}+\frac{1}{c} \right) \le cn^3. $$


1

Let's suppose $n=3^k$. Then we have: $$T(n)=3^kT(1)+2n\log \frac{n^k}{3^{k-1}\cdots3^0}=n+2n\log 3^{k^2-\frac{k(k-1)}{2}} =\\ =n+2n\log n \cdot \frac{\log_3 n+1}{2} $$ Hope it helps.


1

Here is what I get: \begin{align} T(n) &= n + 7T(n/7) \\ &= n + 7(n/7) + 7^2 T(n/7^2) \\ &= n + 7(n/7) + 7^2(n/7^2) + 7^3 T(n/7^3) \end{align} and so on. Each of the summands equals $n$, and there are $O(\log n)$ of them.


1

T(n) = T(√n) + ϴ(log log n) …….1 Let n = 2m Taking log2 both side, we get log2n = m ……2 => (log n) /log 2 = m (using the formula logab = logmb /logma) => log n = m x log2 Now, equation 1 becomes T(2m) = T(2(m/2)) + ϴ(log (m x log2)) => T(2m) = T(2(m/2)) + ϴ(log (m) + loglog2)) As we know that constant can be ignored hence ...


1

Let $S(n) = T(n)/2^n$. Then $$ S(n) = S(n-1) + \frac{4}{2^n}. $$ Since the series $\sum_{n=1}^\infty \frac{4}{2^n}$ converges, we see that $S(n) = \Theta(1)$, and so $T(n) = \Theta(2^n)$.


1

By expansion you can see it is $T(n) = \Theta(2^n)$ (suppose $T(1) = 1$): $$ T(n) = 2T(n-1) +4 = 2(2T(n-2)+4) + 4 = 2^2T(n-2) + 2\times 4 + 4 = \ldots = $$ $$ 2^{n-1}T(1) + 2^{n-2}4 + \cdots + 4 = 4\left(\sum_{i=1}^{n-1}2^i\right) = 4(2^n - 1) $$


1

First, let's review the master theorem: The following theorem can be used to determine the running time of divide and conquer algorithms. For a given program (algorithm), first we try to find the recurrence relation for the problem. If the recurrence is of the below form then we can directly given the answer without fully solving it. If the recurrence is of ...


1

Taking $n=3^k$ we have $$T(n) =3 T(n/3) + \sqrt{n} =3^2T\left(\frac{n}{3^2}\right) +3\sqrt{\frac{n}{3}}+ \sqrt{n} =\\ =3^3T\left(\frac{n}{3^3}\right) +3^2\sqrt{\frac{n}{3^2}}+3\sqrt{\frac{n}{3}}+ \sqrt{n} = \cdots=\\ =3^kT\left(\frac{n}{3^k}\right)+3^{k-1}\sqrt{\frac{n}{3^{k-1}}}+\cdots +3\sqrt{\frac{n}{3}}+ \sqrt{n} =\\ =3^kT(1)+\sqrt{n}\left( (\sqrt{3})^{k-...


1

Your confusion stems from the fact that the MT is often stated in the form $$T(n) = aT(n/b) + f(n),$$ so $b$ is expected to be some constant larger than 1. The recurrence relation you give is not in this form, so to rewrite it to fit the form you know, write $T(n) = 2T(n / (8 / 5)) + 1$ and take it from there.


1

Big O notation hides constant factors. In particular, for every constant $C > 0$, $$ f \in O(g) \Longleftrightarrow Cf \in O(g). $$ In particular, for any $\epsilon > 0$, $$ 20n \in O(n^{1-\epsilon}) \Longleftrightarrow n \in O(n^{1-\epsilon}). $$ This follows directly from the definition of big O. Indeed, suppose that $f \in O(g)$. Then there exist $N,...


1

Let's start with the issue of iteration. Suppose that a function $f$ satisfies $$ f(n/b) \leq (c/a)f(n). $$ Then it also satisfies $$ f(n/b^2) \leq (c/a)f(n/b) \leq (c/a)^2 f(n). $$ You can prove by induction that for all integer $t \geq 0$, $$ f(n/b^t) \leq (c/a)^t f(n). $$ As for your second question, about assuming that $n$ is large enough: the proof is ...


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