New answers tagged

2

An obvious counter example is $g(n) = \sqrt{n}$. If $f(n) = \Theta(\sqrt{\log n})$, you can't conclude that $f(n) = \Theta(\log{\sqrt{n}}) = \Theta(\log{n})$.


1

What you want to prove is false. $T(n) = 16 T(n/4) + n^2\log^3 n$ has solution $T(n) = \Theta(n^2 \log^4 n)$. To see this notice that this recurrence fits in the general form $T(n) = a T(n/b) + f(n)$ once you set $a=16, b=4, f(n)=n^2\log^3 n$. Since $f(n) = n^2 \log^3 n = \Theta( n^{ \log_b a } \cdot \log^k n)$ for $k=3$, you can apply the Master theorem ...


1

Rewrite $\frac{3x^3+2x^2+x+1}{4x^2+1} = \frac{3}{4}x \cdot \frac{12x^3+8x^2+4x+4}{12x^3+3x} = \frac{3}{4}x (1 + \frac{8x^2+x+4}{12x^3+3x})$. Clearly, the limit of $f(x) = \frac{8x^2+x+4}{12x^3+3x}$ for $x \to +\infty$ is $0$ and hence, for any constant $c'>0$, there is a constant $x'_0$ such that $f(x) \le c'$ for all $x \ge x'_0$. Pick your favorite ...


1

Firstly I would revise the inner for loop so that checking whether $r$ has been used already, is $O(1)$. As stated, it is $O(n)$. You could do this by initializing a (1-indexed) boolean array $used[\cdot]$ of length $n$, and setting $used[x]$ equals true whenever you set some $A[i]=x$. Now the question is how many times may $rand()$ be called in the worst ...


2

You swapped two functions. Notice that: $$n^{\sqrt{n}} = 2^{\sqrt{n} \log n } = o(2^{\frac{n}{2}})$$. Once this is fixed, the factorial is in the correct order since very rough inequalities show that $$n! = n \cdot (n-1) \cdot \ldots \cdot 2 \ge \underbrace{2 \cdot 2 \cdot \ldots \cdot 2}_{n-1 \text{ times}} = 2^{n-1} = \omega(2^{\frac{n}{2}}),$$ and $$n = ...


0

Big O is for worst case, but here it seems like you are more interested in average case? It is not really clear how the worst case complexity relates to your measurement, not only for the type of reasons gnasher729 described (caching, branch prediction(!)). For example: Quicksort is worstcase O(n^2), but the average case is O(n*log(n)). When you sample the ...


1

Yes, it has additional information. Consider the following algorithm: "If input N is odd, do something that takes a constant time. If N is even, do nothing." In the odd case, this means that Big O is on the order of 1. In the even case, this means that Big Omega is on the order of 0. This, in turn, means that there is no Big Theta, because there is no ...


4

The Big O notation is not only used to express algorithm complexity. It is also commonly used to express precision of approximations in mathematics. See for example the Stirling's approximation, which uses $O(1/n)$ as a term explaining how good the approximation is. Then you are not necessarily dealing only with functions that grow. Obviously an $f(n) \in O(...


-4

I went and looked it up for this question. "Big Theta" and "Big O" are defined slightly differently, but then found that "Big O" has different definitions depending on where you look. Depending on who you ask, you can have an amortized "Big O" resulting in O(1) where every n operations, it would have to run a linear step rather than a constant and still ...


13

vonbrand's answer is correct in general, but let me add that if $\boldsymbol{f(n)}$ is the running time of an algorithm, then you are correct, $\boldsymbol{O(1)}$ and $\boldsymbol{\Theta(1)}$ are the same. This is because running times of algorithms are positive integers, so the example $f(n) = e^{-n}$ is impossible. As you said, intuitively, nothing grows ...


14

Remember your definitions! As $n \to \infty$ (the use in CS, almost always) $O(\cdot)$ is an upper bound (within a constant multiple, for large $n$), $\Omega(\cdot)$ is a lower bound (within a constant multiple, for large $n$), and $\Theta(\cdot)$ both of the previous. To see the difference, as $n \to \infty$ you have: $\begin{align*} 1 + \lvert \sin n \...


0

As Yuval Filmus and gnasher729 have pointed out my original equation for the repetition structure is indeed wrong. I believe this to be the true correct answer: $\sum_{i=1}^{n} (\sum_{j=1}^{i^2} j)$ $= \sum_{i=1}^{n} (\frac{i^4+i^2}{2})$ $= \frac{1}{2} \sum_{i=1}^{n}i^4 + \frac{1}{2} \sum_{i=1}^{n}i^2$ $\approx \frac{n^5}{10} + \frac{n^3}{6}$ $\...


0

$\Theta$ means we have both a lower bound and an upper bound. For example if $f(n) = \Theta(n^2)$ then $c_1 n^2 <= f(n) <= c_2 n^2$ for large n. However, we have functions that are not always close to the upper bound. For example, $\sin n \cdot n^2 = O(n^2)$, but it is not $\Theta (n^2)$. Still, we cannot reduce the $n^2$. $\sin n \cdot n^2 ≠ o(n^2)$....


3

Here is the original exercise. Suppose we have an algorithm whose running time is $\Theta(n(t + n^{1/t} ))$, where $n$ is the input length and $t$ is a positive parameter we can choose arbitrarily. How should $t$ be chosen (depending on $n$) such that the running time (as a function of $n$) has a minimum rate of growth? As others have pointed out, you ...


2

You want to find $t$ that minimizes $f(t)=t+n^{1/t}$. This can be done by setting the first derivative to zero. In particular, $f'(t) = 1 - (n^{1/t} \log n)/t^2$; setting this to zero yields $n^{1/t} \log n = t^2$, i.e., $(\log n)/t + \log \log n = 2 \log t$. Solving that analytically for $t$ looks tedious but perhaps you can obtain an approximation.


1

Big-oh notations can be added, multiplied, and even exponentiated. But this is very confusing, what does it mean? The best way to think of it is as gnasher729 says: whenever you see $O(n)$ in an expression, you can replace that with some function $f(n)$ which is $O(n)$. For example, $$ O(n) \cdot O(n) $$ means $f(n) \cdot g(n)$, where $f$ and $g$ are some ...


1

I'd take it as a shortcut meaning: There is a function f(n) such that $3^n = 2^{f(n)}$, and f(n) = O (n). Since big-O notation is just a handy shortcut for a rather long statement anyway, your statement is slightly pushing the boundaries, but I'd say it is correct.


1

Yes, this is a valid way to write big O notation, or at least it is used in multiple research papers that I have read. The notation $f(n) = 2^{O(n)}$ means that there exists a constant $c$ such that $f(n) = O(2^{cn})$, or further simplified that there exists a constant $c$ such that $f(n) = O(c^n)$.


4

Sure, that is a correct notation. It is also a correct statement. Essentially it is a compact way to say the following: $\exists c>0, \exists n_0 \ge 0 : \forall n>n_0, 3^n \le 2^{c n} $. You can pick any $c \ge \log_2 3$ and $n_0 = 0$.


3

Yes, your sharp observation is completely correct. To be compatible with the highly strict style shown at section 4.6, Proof of the master theorem of Introduction to Algorithms, here is the complete proposition and a slightly more rigorous proof. It seems that the proof in the question ignores the requirement that $f$ is defined only on exact powers of $b$. ...


0

$n^{0.00001}$ is not approximately $1$. $n^{0.00001}$ goes to infinity as $n \to \infty$. You can see that $\log_2 n = o( n^{0.00001} )$ by taking the limit of their ratio: $$ \lim_{n \to \infty} \frac{\log_2 n}{n^{0.00001}} = \lim_{n \to \infty} \frac{n^{-1}}{0.00001 \cdot n^{0.00001} \cdot n^{-1}} = \lim_{n \to \infty} \frac{100000}{n^{0.00001}} = 0. $$ ...


Top 50 recent answers are included