# Tag Info

9

Put $n=e^s$. Then $n^k=e^{ks}$ and $\log(n)=s$. We know that $$n^k=e^{ks}>2^{ks}=(1+1)^{ks}\geq 1+ks>ks=k\log(n),$$ where the $\geq$ is Bernoulli's inequality. Therefore $\frac{1}{k}n^k>\log(n)$ for $n$ large. Hence $O(n^k)\supset O(\log(n))$.

3

Suppose we start by solving the following recurrence: $$T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + 4n$$ where $T(1) = c$ and $T(0) = 0.$ Now let $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ be the binary representation of $n.$ We unroll the recursion to obtain an exact formula for $n\ge 2$ $$T(n) = c [z^{\lfloor \log_2 n \rfloor}] ... 3 That worked, integration by parts, repeat while patience lasts and the things being integrated are getting smaller;$$ u = \frac{1}{\log \log x}, \; \; \; dv = 1 \, dx  du = \frac{-1}{x \log x \left( \log \log x \right)^2} dx, \; \; v = x, \int \frac{1}{\log \log x} \; dx = \frac{x}{\log \log x} + \int \frac{1}{ \left( \log \log x \right)^2 \; ...

2

In light of the detailed solution of @Marko Riedel, if you only want to show that $T(n)=O(n)$, you can make the (somewhat easier computation): Base case: (ok) Inductive Hypothesis: $T(k)\leq Ck$ for $k<n$ for some constant $c>0$. Then, prove the inductive step: \begin{align*} T(n) &= T(\lfloor(n/2)\rfloor) + T(\lfloor(n/4))+4n \\ &\leq ...

2

$$x\tan(x)=(\epsilon^\alpha x_0+\epsilon^\beta x_1+\epsilon^\gamma x_2+\cdots)^2+\frac{1}{3}(\epsilon^\alpha x_0+\epsilon^\beta x_1+\epsilon^\gamma x_2+\cdots)^4+O(\epsilon^\kappa)=\epsilon$$ and you know that $\alpha<\beta<\gamma<\kappa$ and that $\alpha$ should be chosen to make the largest term on the LHS be $O(\epsilon)$. Expanding gives ...

2

The sum $\Sigma(\cdots)$ is an asymptotic series as $t \to \infty$, so the first two terms of the expansion of $u(x,t)$ as $t \to \infty$ are simply the two terms which do not decrease exponentially, namely $$u(x,t) \sim \underbrace{4t}_\text{first} + \underbrace{2x-10}_\text{second} + \cdots$$ as $t \to \infty$. Now, the first two terms of the ...

1

Your sum expression is not wrong but it is a rather loose bound on the running time. In order to get the desired running time of $n \log n + k + n$ you could use the following sum \begin{align} \sum_{i=1}^k \, (1 + \text{number of items of size $i$}) \end{align} since the inner loop is only executed while there are items of size $i$. You need the ...

1

We have $\sqrt[3]{n^3+an}=n\sqrt[3]{1+\frac{a}{n^2}}$. We expand the latter using Newton's Binomial Theorem to get $$\sqrt[3]{n^3+an}=n\sum_{k\ge 0} {1/3 \choose k} \left(\frac{a}{n^2}\right)^k=n(1+\frac{a}{3n^2}-\frac{a^2}{9n^4}+O(n^{-6}))$$ Repeating, we have $\sqrt{n^2+3}=n\sqrt{1+\frac{3}{n^2}}$, so $$\sqrt{n^2+3}=n\sum_{k\ge 0}{1/2 \choose ... 1 It all comes down to what the definition of f(n)=O(g(n)). Definition A non-negative function f(n) is Big-Oh of g(n), written f(n)=O(g(n)), if there exist constants N and C so that for all n\geq N it follows that f(n)\leq Cg(n). The ability to choose N and C at will is because you only have to show that the inequality works for one ... 1 You want to demonstrate that there are x_0>0 and M>0 such that for all x\geq x_0 |(x^3+2x)/(2x+1)|\leq Mx^2. For large positive x, we have x^3+2x\geq 0 and 2x+1>0 and so$$ \left|\frac{x^3+2x}{2x+1}\right|\leq Mx^2\iff x^3+2x\leq (2x^3+x^2)M. $$Note also that for x\geq 4, x^2\geq 4x. And so M=\frac{1}{2} is enough the rightmost ... 1 Expanding on my hint above, this is one way to prove the result from first principles:$$\frac{x^3 + 2x}{2x + 1} = {x^2 \over 2} - {x \over 4} - {9 \over 8} + {9 \over 8(2x + 1)} \ \ \ \ \ \ - (*) $$hence$$\left|\frac{x^3 + 2x}{2x + 1} \right| \leq {x^2 \over 2 } + \left| x \over 4\right| + {9 \over 8} + \left|9 \over 8(2x + 1) \right| Now we want to ...

1

Every new number rules out the nine numbers $a,2a,3a,4a,5a,a/2,a/3,a/4,a/5$. So there should be at least $\lfloor (p+8)/9\rfloor$ numbers in the set. Perhaps there is overlap, and you can find more.

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