Tag Info

Hot answers tagged

4

You are missing the fact that there must be some constant. The definition is that $f(x)$ is $O(g(x))$ iff there exists some $c$ such that for sufficient large $x$, $|f(x)|\leq c|g(x)|$. So, a hint for the first one is $2^{n+1}=2*2^n$, for the second one you might want to check $x^2$ versus $x$. Does $x^2$ belong to $O(x)$? Hope it helps.


4

The answer can be found in the paper : https://fr.scribd.com/doc/34977341/Sophomore-s-Dream-Function A special function, called "Sophomore's dream" function is defined as : $$\text{Sphd}(\alpha,x)=\int_0^x t^{\alpha t}dt$$ From the properties of this function, an asymptotic expansion is derived Eq.(6:4). The first term, Eq.(9.2) is : ...


3

We know that $f(x) \in \mathcal{O}(g(x))$ if there exist constants $C$, and $k$ so that $$ |f(x)| \le C |g(x)|$$ whenever $n > k$. I will omit the absolute value as it should be clear that $2^\text{r} \ge 0$. (i) Now, $$2^{n+1} = 2 \cdot 2^n $$ so we can take $C = 2, k=1$ to see that $2^{n+1} \in \mathcal{O}(2^n).$ (ii) Assume that $2^{2n} \in ...


3

We can't really ignore the exponent. Expanding the first part, we get: $$ (n\log n + 1)^2 = n^2\log^2 n + 2n\log n + 1 $$ The $n^2\log^2 n$ term dominates all other terms, so we conclude that it is $O(n^2\log^2 n)$.


3

I can give some observations. My guess for changing $x^2+1$ to $2x^2$ is to get rid of the $+1$ and get a monomial (one term) so that taking the log is easier. $x^3$ would not be good because it is asymptotically too fast compared to $x^2+1$. Try following the textbook using $x^3$ instead of $2x^2$ and you'll get an upper bound (big-O notation) that is ...


3

We’re not setting $x^2+1$ to anything. We want to find an upper bound on $\log(x^2+1)$ that can be expressed as a fairly simple function of $x$. Provided that $x\ge 1$, we know that $x^2+1\le 2x^2$, so $\log(x^2+1)\le\log(2x^2)$, and $\log(2x^2)$ can be expressed as a simple function of $\log x$: $$\log(2x^2)=\log 2+2\log x\;.$$ If $x\ge 2$, we know that ...


2

You could have taken $3 x^2$ if you wanted, or $x^3$. You'd end up with the same result. But not $x^2$: it's certainly not true that $x^2 + 1 \le x^2$.


2

All these equality are correct. Recall that $f(x)=_ a O(g(x))$ if $$\exists M>0,\exists \delta>0,\; |f(x)|\le M|g(x)|\;\text{if}\; |x-a|\le \delta$$


2

First we see that a necessary condition to have the limit $e^\alpha$ is that $\lim\limits_{n\to \infty}a_n=0$. Second using Taylor expansion we get $$\left(1+\alpha a_n\right)^n=\exp(n\ln(1+\alpha a_n))\sim_\infty\exp(\alpha na_n)\xrightarrow{n\to\infty}e^\alpha\iff \lim_{n\to\infty}na_n=1\iff a_n\sim_\infty\frac1n$$


1

If $a_n=\frac{1}{n^{\beta}}$, the limit of $(1+\alpha\cdot a_n)^n $ will be $1$ as soon as $\beta >1$. If $\beta =1$, the limit is $e^\alpha$.If $\beta <1$, the limit is $e^\alpha$ would be undefined.


1

Recall that $f(n) = O(g(n))$ iff there exists a constant $c$ and $n_{0} \in \mathbb{N}$ such that $$ f(n) \le c \cdot g(n), \quad \forall n \ge n_{0}. $$ In order to show a big-O notation complexity, it is good to think that you have to find these $c$ and $n_{0}$. In our case, let $$ f(n) = ( n \log{n} + 1)^{2} + (\log{n} + 1)(n^{2}+1). $$ We have ...


1

$f(x)=O(g(x))$ means that $f(x)/g(x)$ is bounded, that is, $|f(x)| \leq c g(x)$ for some constant $c$ and for all $x$ in the domain of both $f$ and $g$. To see through the double $O$ notation, just let $O(\sqrt{x})=g(x)$. Then $f(x)=O(g(x))$, which makes sense. Then $|g(x)|\leq c_2 \sqrt{x}$ for some constant $c_2$. So $$|f(x)|\leq c_1 |g(x)| \leq c_1c_2 ...


1

My first impulse would be to note that $$\frac{T(n)}n=\frac{T(n/2)}{n/2}+\frac1{\log n},$$ and that to be able to iterate this requires to look at the powers of $2$, since the new sequence $$S(k)=\frac{T(2^k)}{2^k}$$ solves the recursion $$S(k)=S(k-1)+\frac1{k\log 2},$$ from which I readily see that $$S(k)=S(0)+\frac1{\log ...


1

It seems the following. Let $f(n)=n!$. Then $f'(n)=(n+1)!-n!=n\cdot n!$. So $f=O(f')$, but $f \not= \ \theta(f')$



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