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 ...


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(...


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 = ...


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 ...


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 ...


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