# Tag Info

7

Hint: $\sin n \geq -1$, so $8^{\log_2 n}+1+\sin n\geq 8^{\log_2 n} = n^3$.

4

The inner (count += 1) operation is executed approximately $$n+\frac{n}{2}+\frac{n}{4}+\cdots=n\left(1+\frac{1}{2}+\frac{1}{4}+\cdots\right)=2n$$ times.

4

The outer loop isn't looping through all linear values from n to 0. It is halving each time. So it goes: $n, \frac{n}{2}, \frac{n}{4}, \frac{n}{8}, \frac{n}{16}, ...$ The inner loop is called this many times so you need to work out $n+\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\frac{n}{16}+... = 2n$. Hence its $O(n)$.

4

Every NP-complete problem is also a NP problem, by definition. Therefore, if NP=P, the same will be true for NP-complete problems. You can't say the same for NP-hard problems. These problems include all problems harder then NP problems, except for the NP-complete problems. In this case, we have that NP-hard $\cap$ NP = NP-complete. So, even if NP=P, we ...

3

Use equivalents: $$\left.\begin{array}{l}f(n)\sim_\infty50 n\log n\\ g(n)\sim_\infty 10 n,\end{array}\right\}\enspace\text{hence}\enspace\frac{f(n)}{g(n)}\sim_\infty \frac{50n\log n}{10 n}=5\log n\xrightarrow[n\to\infty]{}+\infty.$$

3

This is not a complete answer, but rather meant to give you an idea of what to think about. The first thing to recognize is that the problem is singular: for $\epsilon=0$ there are only two roots (counting multiplicities) but for $\epsilon>0$ there are three roots (counting multiplicities). As a result, you should expect two roots which are close to the ...

3

Since $k$ is assumed to be a constant, then you are basically comparing a polynomial growth ($n^{O(1)}$) to a superpolynomial one ($n^{\omega(1)}$). An idea of the proof: $n^k\log(n^k) = k n^k\log n = o(n^{k+1})$ $(k+1)\log n = o(\log^2 n)$ $n^{k+1} = 2^{(k+1)\log n}$, while $n^{\log n} = 2^{\log^2 n}$

2

Note that you have an endpoint maximum, and hence the integral should only be one-sided; this is the sort of case where Watson's lemma applies.

2

Your idea goes in the right direction, but doesn't quite work out. If we choose a branch of $\sqrt{z}$ on a domain where one exists, and expand $e^{\sqrt{z}}$, we get $$\sum_{n = 0}^\infty \frac{(\sqrt{z})^n}{n!} = \sum_{k = 0}^\infty \frac{(\sqrt{z})^{2k}}{(2k)!} + \sum_{k = 0}^\infty \frac{(\sqrt{z})^{2k+1}}{(2k+1)!} = \sum_{k = 0}^\infty ... 2 Outline (rather messy: is there a more elegant approach?): First, prove that you must have x=x(\epsilon)\xrightarrow[\epsilon\to\infty]{} 0. Then, you can get the expansion one term at a time... Now, the second bullet (up to order two) below -- if I have not screwed up.$$ 1-2x + x^2+\epsilon x^3 = 1+\epsilon x^3 + o(1) $$so you need \epsilon x^3 ... 1 You seem to have two distinct questions -- one in the title, regarding exponentiation, and the other in the body, regarding symmetry of the \Theta(\cdot) notation. Question in the title: "if f(n)=\Theta(g(n)), do we have 2^{f(n)}=\Theta(2^{g(n)})?" No. Take f(n)=n, g(n)=2n. Do we have 2^{n} = \Theta(2^{2n})? Question in the body: "if ... 1 By substituting \epsilon=1/n^{1/p} we see that $$\inf_{\epsilon > 0} \bigg\{4\epsilon + \frac{24}{\sqrt{n}(2-p)\epsilon^{\frac{p}{2}-1}} \bigg\} \leq \left(4+{24\over 2-p}\right) {1\over n^{1/p}}= \mathcal{O}\bigg(\frac{1}{n^{\frac{1}{p}}}\bigg),$$ 1 You may set x=1/y and multiply the equation$$\epsilon x^{2}+2x-4=0\tag{1}$$by y^2 and obtain:$$\epsilon +2y-4 y^2=0\tag{2}$$This probably answers your question. But in your original example, \epsilon appears both in the leading order term and trailing order term. So the above method do not work. We first rewrite it as:$$\epsilon ...

1

Part of the problem lies in realizing which roots are regular and which roots are singular. In this problem, one of the roots is actually regular: this root is a perturbation of the one root of $2x=0$, i.e. of $x=0$. This occurs in a regime where $\epsilon x^2$ is of smaller order than $2x$, so that the dominant term in the expression $\epsilon ... 1 For the first code, you are correct in observing that the inner-most for loop runs once every time the second for loop runs, as$j=0\mod i$only when$j=i$, so the time complexity is$\Theta(n^2)$. For the second code, observe that the inner-most for loop runs$i$times every time the second for loop runs. Hence the inner-most loop runs$\Theta(n^2)$times, ... 1 I think the first one is right but not for the right reason. The if triggers exactly once for each revolution of the outer loop. But for the second that "if" line removes all but 1 out of every$i$of the$j$s. So the inner loop only runs approximately$1/n$of the time. Should give us$O(n^3)$instead. 1 That integral can be computed in a explicit way by using modified Bessel functions of the first kind: $$\int_{0}^{\pi/2} e^{-\lambda\sin(x)^2}\,dx = \frac{\pi}{2}e^{-\lambda/2}\,I_0(\lambda/2) \tag{1}$$ then the asymptotic form follows from Hankel's expansion: $$\int_{0}^{\pi/2} e^{-\lambda\sin(x)^2}\,dx \approx \sqrt{\frac{\pi}{4\lambda ... 1 You can take advantage of the symmetry of your integrand to make the maximum point an interior point: I(\lambda)=\int_0^{\pi/2} e^{-\lambda\sin^2(x)}\,dx ={1\over 2}\int_{-\pi/2}^{\pi/2}e^{-\lambda\sin^2(x)}\,dx. Laplace's Method then yields I(\lambda)\sim \sqrt{\pi\over 4\lambda}. This is consistent with your exact evaluation of I(\lambda) and the ... 1 Simple manipulations show that$$x=\frac {\log n}{W(\log n)} \sim \frac {\log n}{\log\log n}$$where W is Lambert W function. Edit:$x\log x=\log n\Rightarrow \log x = W(\log n)\Rightarrow x=e^{W(\log n)}=\frac {\log n}{W(\log n)}\sim\frac {\log n}{\log\log n-\log\log\log n}\$.

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