2022 Developer Survey is open! Take survey.

# Tag Info

## Hot answers tagged asymptotics

6 votes
Accepted

$$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)... • 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 ... • 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 ... • 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^... 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. 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)\... • 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 ... 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. • 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 ... • 1,005 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).
• 3,337

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