# Tag Info

27

Is what I wrote about big-O correct? Yes. How do big-Theta sets relate to each other, if they relate at all? They are a partition of the space of functions. If $\Theta(f)\cap \Theta(g)\not = \emptyset$, then $\Theta(f)=\Theta(g)$. Moreover, $\Theta(f)\subseteq O(f)$. Why do they relate to each other the way they do? The explanation is probably ...

18

We have $$\frac{n!}{(n/2)!(n/4)!\cdots 2!} = \frac{n!}{(n/2)!(n/2)!} \frac{(n/2)!}{(n/4)!(n/4)!} \cdots \frac{4!}{2!2!} \frac{2!}{1!1!} = \\ \binom{n}{n/2} \binom{n/2}{n/4} \cdots \binom{4}{2} \binom{2}{1} \leq 2^n 2^{n/2} \cdots 2^4 2^2 = 2^{n+n/2+\cdots+2+1} <2^{2n} = 4^n.$$ Using Stirling's approximation we can get more refined asymptotics, but we ...

16

In order to compare 2 complexities just calculate a limit of their ratios as below: \displaystyle\begin{align*} \lim_{n\to\infty}\frac{n^2log(n)}{n^2\sqrt{n}} &= \lim_{n\to\infty}\frac{log(n)}{\sqrt{n}} = \lim_{n\to\infty}\frac{log(\sqrt{n})^2}{\sqrt{n}} = \lim_{n\to\infty}\frac{2log(\sqrt{n})}{\sqrt{n}} \\ &\underset{\left| k = \... 12O(n^2 \times \log(n))$is greater than$O(n^2)$but it is smaller than$O(n^{2 + \epsilon})$for any$\epsilon > 0$, however small$\epsilon$is (see here). In particular, it is smaller than$O(n^{2.5})$. You're basically comparing the growth of$\log$and square root. 9 Is it true that every algorithm with runtime complexity of$T(n)=\Omega(n)$satisfies that$T(n)=\Theta(f(n))$for some convex function$f$? No. A simple example is $$T(n)=\begin{cases}n & \text{ when } n \text{ is odd,}\\ n^2 & \text{ when } n \text{ is even.} \end{cases}$$ What if we also require$T(n)$be strictly increasing? The answer is ... 7 You can estimate your sum from below by $$1^k + \cdots + n^k \geq \sum_{m=\lceil n/2 \rceil}^n n^k \geq \frac{n}{2} \cdot \left(\frac{n}{2}\right)^k = \Omega(n^{k+1}).$$ It is even easier to see that$1^k + \cdots + n^k \leq n^{k+1}$, and so$1^k + \cdots + n^k = \Theta(n^{k+1})$. You can get better bounds by approximating the sum with an integral: $$\... 7 "On the order of" is an informal statement which really only means "approximately". Big O notation is a precise mathematical formulation which expresses asymptotic behavior, not approximate values of a function (e.g., 10n \in O(n), despite 10n being 10 times as larger as n). They can hardly be considered the same things. What the lecturer is trying to ... 7 The function n^{1/\log \log n} tends to infinity, since$$ n^{1/\log\log n} = e^{\log n/\log\log n}, $$and \log n/\log \log n \longrightarrow \infty. 6 The wikipedia page suggests using Newton-Raphson Division to get O(M(n)). The way Newton-Raphson Division works is by finding the solution x of \frac{1}{x}-b=0 (so that x=1/b), and then returning ax. A Newton-Raphson iteration in general is$$ x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)}. $$In this case f(x)=\frac{1}{x}-b and f'(x)=\frac{-1}{x^2}... 6 After checking this post again, I'm surprised this isn't on here yet. Domain Transformation / Change of Variables When dealing with recurrences it's sometimes useful to be able to change your domain if it's unclear how deep the recursion stack will go. For instance, take the following recurrence:$$T(n) = T(2^{2^{\sqrt{\log \log n}}}) + \log \log \log n$...

6

The difference is IMHO well explained in that book, the part you are referring to says The number of anonymous functions in an expression is understood to be equal to the number of times the asymptotic notation appears. So this $$\sum_{i=1}^n O(i)$$ means a placeholder for $$\sum_{i=1}^n f(i),$$ where $f(i)$ is an anonymous function from the set $O(... 6 Doc Brown answered your first question perfectly. Let me answer your second question. The expression$O(i)$is a placeholder for a function which is bounded by$Ci$for some$C > 0$. Therefore $$\sum_{i=1}^n O(i) \leq C \sum_{i=1}^n i = C \frac{n(n+1)}{2} = O(n^2).$$ Furthermore, this bound is tight, in the sense that$n^2$cannot be replaced with any ... 6 If the$O$-complexity given is true, then$f(x)\leq c_2n\log n$will not always be true. So in this case, how is$\Theta$-complexity different from$O$-complexity? Yuval has covered the quicksort aspects of your question but you have a couple of fundamental misunderstandings about asymptotics. There is no such thing as "$\Theta$-complexity" or "$O$-... 6 You should be very careful when summing up a variable number of terms in asymptotic notation, as the result actually depends on the hidden constants. Consider the following example:$f_i(n) = i\cdot n$for all integers$i$and$n$. Then, for any integer$i$,$f_i(n) \in O(n)$. If you are not careful, you could end up writing something like: $$\sum_{i=1}^n ... 5 Let f(n) = n/\log n, and denote by g(n) the number of applications of f it takes to get n below some arbitrary constant. On the one hand, f^{(t)}(n) \geq n/\log^t n, and so$$ g(n) \geq \log_{\log n} n = \frac{\log n}{\log \log n}. $$To obtain an upper bound, notice that as long as f^{(t)}(n) \geq \sqrt{n}, we have \log f^{(t)}(n) \geq (\log n)/... 5 If T(1)\le 6 and T(2)\le 12, we can show that T(n)\le 6n by induction.$$T(n) = T(n/2) + T(n/3) + n \le 6(n/2)+ 6(n/3)+n= 6n.$$More generally, let c\gt6 be a constant such that T(1)\le c and T(2)\le 2c, then we can prove routinely that T(n)\le cn. Although it might seem unbelievable to you, it is true that$$T(n)=O(n).$$Intuitively, ... 5 We can lower bound the sum roughly by$$ \sum_{i=1}^n i(n+1-i) \geq \sum_{i=n/3}^{2n/3} (n/3)^2 \geq (n/3)^3. $$This shows that it is \Omega(n^3). Since each summand is at most n^2, the sum is also O(n^3). We can also compute the sum explicitly:$$ \sum_{i=1}^n i(n+1-i) = (n+1) \sum_{i=1}^n i - \sum_{i=1}^n i^2 = (n+1) \frac{(n+1)n}{2} - \frac{n(n+1)(... 5 If$f(n) = \Theta(g(n))$, then in particular$f(n) = O(g(n))$. This is just like saying that if$x = y$, then in particular$x \leq y$. Suppose that$f(n) = O(g(n))$. According to the definition, there are$N,c$such that all$n \geq N$satisfy$f(n) \leq cg(n)$. Taking logarithms, this implies that$\log f(n) \leq \log c + \log g(n)$. Does this imply the ... 5 You can calculate the limit of the function for$n\to\infty: \begin{align} \lim_{n\to\infty}\frac{n\cdot7^n+\frac{8}{n!}}{(n+7)\cdot7^n}&=\lim_{n\to\infty}\frac{n\cdot7^n}{(n+7)\cdot7^n}+\lim_{n\to\infty}\frac{\frac{8}{n!}}{(n+7)\cdot7^n}\\ &=\lim_{n\to\infty}\frac{n}{n+7}+\lim_{n\to\infty}\frac{8}{(n+7)\cdot7^n\cdot n!}\\ &=1 + 0\\ &=\Theta(... 5 From this post, you can approximate\log(1+x)$with$x$for little values of$x$. Hence, $$f(n) \sim \frac{1}{\frac{1}{2^n-1}} = 2^n-1$$ Therefore, you can't find any constant$c$, such that$f(n) = O(n^c)$, as it is$\Theta(2^n)$. 5 As$n^{0.5}$is always greater than$\log(n)$,$O(n^{2.5})= O(n^2 \times n^{0.5})$is always bigger than$O(n^2 \times \log(n))$. Anyway, you should consider your real algorithm usage scenario to choose one which fits the best. 5 Your expression is $$E = \frac{cn^2}{\log \frac{n(n+1)}{2}}$$ where$c$is some constant. The simple upper bound for$E$is $$E\le c n^2$$ which implies that$\mathcal{O}(n^2)$. For a better bound $$E = \frac{cn^2}{\log \frac{n(n+1)}{2}} = \frac{cn^2}{ 2 \log n + \log n - \log 2 }$$ Now it is an easy verification that$E$is$\mathcal{O}(\frac{n^...

4

Let $S(n) = T(n)/n$. Then $S(n)$ satisfies the recurrence $$S(n) \leq \frac{1}{2} S\left(\frac{n}{2}\right) + \frac{1}{3} S\left(\frac{n}{3}\right) + 1.$$ In particular, if $C$ satisfies $$\frac{1}{2} C + \frac{1}{3} C + 1 \leq C$$ then $S(n/2),S(n/3) \leq C$ would imply $S(n) \leq C$. This is the case for all $C \geq 6$.

4

Best case is $O(1)$, that is when you find the element in the first check. Worst case is $O(n)$, and it happens when the element is in the first position, and in each check you get the last position, thus going through the whole array. Average case is a little bit more tricky to get, since we need to solve a recurrence to get the expected value. Let $T(n)$ ...

4

There are constants $c,C,\epsilon > 0$, such that $1+x+cx^2 \le e^x \le 1+x+Cx^2$ whenever $|x| \leq \epsilon$.

4

You can write an interpreter for any reasonable instruction set usin a single loop with a very, very long if/ else if / else if... statement. That should cover about all solvable problems. You can calculate the Ackerman function with one loop without recursion (not in the lifetime of the universe for n >= 4, but in principle).

4

Not every recurrence falls within the bounds on the master theorem. Your recurrence is an example. However, by unrolling your recurrence, we can come up with an explicit formula: $$T(n) = 6(n+1) + T(n-1) = 6(n+1) + 6n + T(n-2) = \cdots = \\ 6(n+1) + 6n + \cdots + 6\cdot 2 + T(0) = \\ 6(n+1) + 6n + \cdots + 6\cdot 2 + 6\cdot 1 = \\ 6 \sum_{m=1}^{n+1} m = 6\... 4 What the equation means is that there exist constant A>0 and B,C such that$$ |x| \leq A \Longrightarrow Bx^2 \leq e^x-1-x \leq Cx^2. $$In particular, for small x, e^x is very close to 1+x, since the error is only O(x^2) (when x is small, x^2 is much smaller than x). The same estimate doesn't hold for large x — indeed, e^x ... 4 No. Consider, for instance,$$T(n,m) = \begin{cases} m, & \text{$m$ even} \\ \frac{m}{n}, & \text{$m$ odd} \end{cases} and notice $\frac{m}{f(n)} \le T(n, m) \le m$ holds for $f(n) = n$. Suppose $T(n,m) \in \Theta(m g(n))$ for some $g(n)$, that is, there are $c, c' > 0$ with $cmg(n) \le T(n,m) \le c'mg(n)$ for all but finitely many $m,n$. Since ...

4

The worst-case running time of quicksort is $\Theta(n^2)$, and therefore quicksort always runs in $O(n^2)$, and this bound is tight (that is, best possible). The average-case running time of quicksort is $\Theta(n\log n)$. The best-case running time of quicksort is also $\Theta(n\log n)$, and therefore quicksort always runs in time $\Omega(n\log n)$, and ...

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