Tag Info

Hot answers tagged

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