2022 Developer Survey is open! Take survey.
6 votes
Accepted

An α-good tree with n nodes has height O(log n)

$$2|y| = (|y|-|z|) + (|y|+|z|)\le \alpha |x| + |x| - 1.$$ So, $|x| \ge \frac2{1+\alpha}|y|$. Since $y$ is an arbitrary child of $x$, if node $x$ is of height $k$, $|x| \ge \left(\frac2{1+\alpha}\right)...
user avatar
  • 33.1k
5 votes

An α-good tree with n nodes has height O(log n)

First, note that if $T$ is an $\alpha$-good tree, then for any node $x$ with children $y$ and $z$, without loss of generality, $|y| \leqslant |z| <\frac{1+\alpha}2 |x|$. Now consider $h_n$ the ...
user avatar
  • 7,154
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
  • 33.1k
3 votes

Why is $a^{\log_b n}$ the same as $n^{\log_b a}$?

We can say some number $a = b^{\log_b(a)}$, because $\log_b(a)$ tells us to how much power we need to raise $x$ to get $a$ and then we actually raise it to get $a$. Then, $$a^k = (b^{\log_b(a)})^k = b^...
user avatar
3 votes

Why is $a^{\log_b n}$ the same as $n^{\log_b a}$?

Take $\log_b$, and you get $\log_b n \cdot \log_b a$ on both sides.
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,154
2 votes

A little confusion with Big Theta time complexity

If $f(n) \in O(g(n))$ and $g(n) \in O(f(n))$ then $f(n) \in \Theta(g(n))$, otherwise $f(n) \not\in \Theta(g(n))$. $n^2 \in O(n^3)$ but $n^3 \not\in O(n^2)$ so $n^2 \not\in \Theta(n^3)$. It works ...
user avatar
2 votes

equivalency of some facts in $O$ notation

Let $a>b>0$. From $\log(a+b)=\log(a)+\log\left(1+\dfrac ba\right)$, we draw $$\log(a)\le\log(a+b)\le \log(a)+\log(2)$$ and similarly for $b>a$.
user avatar
  • 3,337
1 vote

Why is $a^{\log_b n}$ the same as $n^{\log_b a}$?

The first result that will be useful is $\ln x^r = r \ln x$, where $\ln$ is the natural logarithm. When the base of the logarithm changes to a different number $a$, the logarithm can be rewritten as ...
user avatar
1 vote

Why is $a^{\log_b n}$ the same as $n^{\log_b a}$?

$$p^{\log(q)}=e^{\log(p)\log(q)}=q^{\log(p)}$$ holds (also for other bases).
user avatar
  • 3,337

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