# Tag Info

6

The expression $$\sum_{n=0}^\infty \frac{n^2}{2^n}$$ is constant. Therefore there are two options: The expression is not well-defined. This would happen, for example, if the series diverges. The expression is well-defined, in which case it is $O(1)$ (since any constant is $O(1)$). One fine point is that in computer science, we often only consider ...

6

It is false that $$\sum_{n=0}^\infty \frac{n^2}{2^n} \ge \left( \sum_{n=0}^\infty n^2 \right) \cdot \left( \sum_{n=0}^\infty \frac{1}{2^n} \right),$$ assuming that's what you meant. You can see that the first series on the right side diverges while the second converges to a positive constant. To show that $\sum_{n=0}^\infty \frac{n^2}{2^n} = O(1)$ you can ...

6

Let me suggest direct simple solution: definition of $\Omega$ contains $2$ bound variables $c$ and $N$. In simple cases, as is in OP, we can choose one and solve second from expression obtained from definition. Obviously for left side we need constant less then one, so taking, for example, $c=\frac{1}{10}$ we have $$n^{5}-3n^{4}+\log\left(n^{10}\right) \... 5 Just apply the definition. So in this case, we must have that \lim_{n \to \infty} f(n) / g(n) > 0 in order for f(n) = \Omega(g(n)). Let's plug in what you have and observe that$$\lim_{n \to \infty} \frac{n^{5}-3n^{4}+\log(n^{10})}{n^5} = 1 > 0.$$This completes the proof. 4 Suppose that \log^* n = k. This means it takes k many \log's to reduce n below some constant. Therefore \log^* \log n = k-1 (assuming k is not too small), whereas \log \log^* n = \log k. 4 Definitions I'm using the definition of big-omega from Wikipedia and making it more explicit:$$\left[ f(n) \in \Omega(g(n)) \right] \:\Longleftrightarrow\: \left[ \exists k \in \mathbb{R}^+, \exists n_0 \in \mathbb{N}, \forall n \in \mathbb{N}, \left[(n > n_0) \Rightarrow (f(n) \ge k \cdot g(n)) \right] \right]$$In your statement you have f(n) = n^5 - ... 3 You are indeed correct that it isn't n^n (though this is good enough for most purposes). As OmG mentioned in the comments, there is a standard approximation formula called "Stirling's approximation formula" which gives the following asymptotic bound:$$n!=\Theta\Big(\sqrt{n}\frac{n^n}{e^n}\Big)$$3 Suppose f_1(n)=\log \log^{*}(n), and f_{2}(n)=\log^{*} \log(n). Let n=2^m then According the definition of iterated function: \log^* n (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1. So$$f_1(2^m)=\log \log^*(2^m)=\log \log^*\log(2^m)+1=\log\...

2

First, simplify $f(x)$ conditions: $$f(x) = \begin{cases} 8f(x/2) + Θ(1) & \text{ if } x > \sqrt{M}, \\ M & \text{ if } x\leq \sqrt{M}. \end{cases}$$ Now, if you draw recursion tree $\mathbb{T}$ of $f(x)$, each internal node has $8$ children, on other hand, the height of $\mathbb{T}$ $$\log_2 x-\log_2 \sqrt{M}=\log_2 \left(\frac{x}{\sqrt{M}}\... 2 Suppose n=2^k. By substitution method we can extend the recurrence relation as follow:$$T(n)=T(\sqrt{n})+\log\log n=\hspace{4pt} T\left(\sqrt{\sqrt{n}}\right)+\log\log n+10\log\log\sqrt{n}=\hspace{4pt} T\left(\sqrt{\sqrt{\sqrt{n}}}\right)+\log\log n+\log\log\sqrt{n}+\log\log\sqrt{\sqrt{n}}\dots =\hspace{4pt}T\left(n^{\frac{1}{2^k}}\right)+\...

2

The lower bound of $$T(n)\mathcal={\Omega}(n^3).$$ Because of $T(n)$ have a term $n^3.$ To find the upper bound we can use induction: $$T(n)\leq cn^3$$ $$=3cn+n^3\leq cn^3$$ As $n\to \infty$ , and for all $c\geq 3$ $$=3cn+n^3\leq cn^3.\hspace{10pt}\square$$ So $$T(n)=\theta(n^3).$$

2

Consider a tree $\mathcal{T}$ at root $\mathcal{r }$, and contain $\mathcal{n}$ nodes and $\mathcal{h}$ be height of $\mathcal{T}$ such that leaves are half full, so, without loss generality, suppose the left sub-tree $\ell$ of $\mathcal{T}$ is a full binary tree (i.e. leaves are half full). (i) Now it's sufficient to show that ratio of $\ell$ to $n$ (i....

2

Let $T,S$ defined using the same recurrence, but using two different initial conditions: $T(1) = 1$ and $S(1) = 2$. A simple induction shows that $T(n) \leq S(n)$. On the other hand, consider the recurrence $R(n) = 2R(\lfloor n/2 \rfloor) + n/2$, with initial condition $R(1) = 1$. A simple induction shows that $R(n) = S(n)/2$ and that $R(n) \leq T(n)$, and ...

2

Suppose $f(n)=n^4,g(n)=n$, so $$\lim_{n\to\infty}\frac{f(n)}{g(n)}=\frac{n^4}{n^3}=\frac{n^3}{1}=\infty.$$ That means $f(n)=\Omega(g(n))$ and $f(n)\neq\mathcal{O}(g(n)).$ As a result, if $f(n)=\omega(g(n))$, then we can conclude that, $f(n)=\Omega(g(n))$ and $f(n)\neq \mathcal{O}(g(n)).$ Note that in a such case that $$\lim_{n\to\infty}\frac{f(n)}{g(n)}=\... 2 Your counter-example isn't true. Let f(n)=2^n, we see that$$f(\frac{n}{2})=2^\frac{n}{2}=\sqrt{2}^n.$$As a result we show that f(n)\neq\Theta(f(\frac{n}{2}))$$\lim_{n\to \infty}\frac{f(n)}{f(\frac{n}{2})}=\frac{2^n}{\sqrt{2}^n}=\frac{2}{\sqrt{2}}\times\dots\times\frac{2}{\sqrt{2}}=\frac{\sqrt{2}}{1}\times\dots\times\frac{\sqrt{2}}{1}=\...

1

Your basic idea is good. Here is how you would approach it: Let us assume towards contradiction that $\exists c_2,n_0:\forall n>n_0:f(n)\le c_2\cdot g(n)$ In particular, we can re-write this as: $$\exists c_2,n_0:\forall n>n_0:\frac{f(n)}{g(n)}\le c_2$$ Now, since $\lim_{n\rightarrow \infty}\frac{f(n)}{g(n)}=\infty$, then we know by definition of the ...

1

Here is a quick formal proof without limits. Choose $c=\frac{1}{4}$ and $n_0=4$. For $n \ge n_0$: $$n^{5}-3n^{4}+\log n^{10} > n^5 - 3n^{4} = n^4 \cdot (n-3) \ge n^4 \cdot \frac{n}{4} = \frac{n^5}{4} =c n^5,$$ where we used the inequality $n-3 \ge \frac{n}{4}$ or, equivalently, $\frac{3}{4}n \ge 3$.

1

With small $n$ Big $\Omega$ it is just about useless and it's the hidden constants, so we suppose $n\to \infty$. At this situation, the term $n^5$ dominate other terms, and we can conclude that $n^5=\Omega(n^5)$. Note that, if number of functions are constant ( in the below $k$ is constant) that has below form: $$f_1(n)+\dots+f_k(n)$$ and suppose $f(n)$ is ...

1

Suppose that you are running MAX-HEAPIFY on some vertex $v$ of a heap $H$. Then the subtree $H_v$ rooted at $v$ is also a heap. Let $n$ be the number of vertices of $H_v$. Clearly if $v$ has no children or only one (left) children then $T(n) = O(1)$ so let's focus on the case in which $v$ has two children $u$ and $w$, where $u$ is the left child and $v$ is ...

1

From the definition of big-O: $$f(n)=\mathcal{O}(n)$$ if there exists a positive constant real number $c$ that $$f(n)\leq cn.$$ I claim that $$\frac{n}{\log n} \log \frac{n}{\log n} = \mathcal{O}(n)$$ So, for proving it we act as follow $$\frac{n}{\log n} \log \frac{n}{\log n} \leq cn$$ multiply each side of inequality by ${\log n}$: $$n \log \frac{n}{\... 1 Usually, when considering machine learning algorithms from a theoretical perspective, we are interested in PAC learnability, or some other learnability definition (most of those are very similar to PAC, since everything in the machine learning region is stochastic). Under those definitions, there are a few possible "metrics" that measure something ... 1 Suppose n=2^k. Because of lim_{n\to \infty}\frac{n}{\frac{n}{\log n}}=\infty, you can rewrite T(n) as follow:$$T(n)=\sqrt{n}T(\sqrt{n})+\mathcal{O}(n).$$By substitution method:$$T(n)=\sqrt{n}T\left(\sqrt{n}\right)+\mathcal{O}(n)=\sqrt{n}\left(\sqrt{\sqrt{n}}T\left(\sqrt{\sqrt{n}}\right)+\sqrt{n}\right)+n\dots=n^{\frac{1}{2}+\frac{1}{4}...

1

Let $\ell_x$ be the left sub tree at node $x$, Let $r_x$ be the right sub tree at node $x$. So the size of $\ell_x$ is $\mid\ell_x\mid$, and size of $r_x$ is $\mid r_x\mid$. Let $T(n)$ be number of nodes our procedure visited during in-order traversal. So when you recurs on the left sub tree at node $x$, the size of problem is $T(n-1-\mid r_x\mid)$, because ...

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