# Tag Info

12

The two phrases The running time is $O(n^2)$ and The running time is at most $O(n^2)$ mean the same thing. This is similar to the following two equivalent claims: $x = y$ for some $y \leq z$. $x \leq y$ for some $y \leq z$. Why would we ever use "at most $O(n^2)$", then? Sometimes we want to stress that the bound $O(n^2)$ is loose, and then ...

10

“At most” might mean “at worst” i.e. that the worst-case time complexity is $O(n^2)$. For example one might say that “Quicksort is at most $O(n^2)$,” meaning that no matter what infinite subset of the inputs you look at, the complexity on that subset is never more than $O(n^2)$.

6

My reading is that it's not necessarily a tight bound, ie. we know the algorithm is $O(n^2)$, but we don't know if it's (for example) $O(n^{1.99})$

4

"f(n) is in O(n^2)" means f(n) ≤ cn^2 for all large n and for some c > 0. Clearly if f(n) ≤ cn^2, then f(n) ≤ cn^3, cn^4 etc. So factually, "f(n) is in O(n^4)" is equally true. It just gives you much less information, so it may be less useful. If someone says "f(n) is at most O(n^2)", I would interpret that as "I proved ...

4

We say that a function $f(n)$ is $O(n^2)$ if there exist constants $C,N>0$ such that $f(n) \leq Cn^2$ for all $n \geq N$. We usually denote "$f(n)$ is $O(n^2)$" by "$f(n) = O(n^2)$". An algorithm has running time $O(n^2)$ if its worst-case running time is $O(n^2)$. That is, if we denote by $T(n)$ the maximum running time of the ...

2

Having, for non negative case, formal definition $$O(f)=\{g: \exists C>0, \exists N \in \mathbb{N}, \forall n>N, g(n) \leqslant Cf(n)\}$$ then we of course are considering big-$O$ as set. If some $g \in O(n^2)$, then words "the running time on the input is bounded from above by the $\text{value of f(n)}$" means, as it is in definition, ...

2

You just need to show that $$\lim_{n \to \infty} \frac{\log^r n}{n^p} = +\infty.$$ This is trivial if $r \le 0$ since $\frac{\log^r n}{n^p} = \frac{1}{n^p \log^{-r} n}$ and $\lim_{n \to \infty} n^p \log^{-r} n = +\infty$. For $r>0$, you can use l'Hôpital's rule $\lceil r \rceil$ times to obtain: $$\lim_{n \to \infty} \frac{\log^r n}{n^p} = \lim_{n \... 2 Classical way is same as when we consider double limit \lim\limits_{(n,m) \to \infty}f(n,m)=A, which use intention to infinity by squares i.e. for \forall \varepsilon>0 \exists \delta>0 such that for \forall n > \delta and \forall m > \delta holds |f(n,m)-A|< \varepsilon. Using maximum norm conception we can write \left\Vert(m,n)\... 1 I understand it so, that, perhaps, saying "f is at most O(n^2)", the speaker wants to emphasize, exaggerate his attitude to upper bound O(n^2) as least one. Good point anyway. 1 For sure, T(\sqrt{n})\leq T(n), so T(n)\leq 2T(n-1)+n, but this produces an exponential upper bound, which is correct but to big to be useful. Anyway, in this case if we start from the solution of the recurrence S(n)=S(n-1)+O(n), which is O(n^2), we observe that S(\sqrt{n})=O(n), so also the solution of T(n)=T(\sqrt{n})+T(n-1)+O(n) is in O(n^2).... 1 More interesting than solving the recurrence is to show where exactly your complete induction proof went wrong. To show a statement S(n) by complete induction you prove manually that S(n) is true for all n ≤ n_0 for some n_0, and then you show that for n > n_0, if S(n') is true for all n' < n, then S(n) is also true. That's a quite general form ... 1 Ok lets try solving this by substitution , T(n) = 2T(n-1) + 1 from this we know , T(n-1) = 2T(n-2) + 1 so T(n) = 2(2T(n-2) + 1) + 1 T(n) = 2^2T(n-2) + 3 lets substitute one more time T(n-2) = 2^2T(n-3) + 1 T(n) = 2^2(2T(n-3)+1) + 3 T(n) = 2^3 T(n-3) + 7 Hopefully you can notice the pattern now T(n) = 2^{k}T(n-k) + 2^{k}-1 So , for k = n T(... 1 First, let's review the master theorem: The following theorem can be used to determine the running time of divide and conquer algorithms. For a given program (algorithm), first we try to find the recurrence relation for the problem. If the recurrence is of the below form then we can directly given the answer without fully solving it. If the recurrence is of ... 1 What is the running time of an algorithm? To answer this question, we need to specify an exact computation model with a cost for each operation. Whatever computation model you choose to use, it is highly unlikely that the running time of an algorithm on an input of size n is exactly n. It is far more likely to be of the form an+b for some constants a,... 1 Let's consider only r>0. For \ln(n)^r \in o(n^p),p>0 is enough to show \ln(n) \in o(n^\alpha), for \frac{p}{r}=\alpha>0, because \frac{\ln(n)^r}{n^p} =\left(\frac{\ln(n)}{\sqrt[r]{n^p}}\right)^r and r power is continuous function. So we come to limit$$\lim\limits_{n \to \infty}\frac{\ln(n)}{n^\alpha}=\lim\limits_{n \to \infty}\frac{\...

1

The most reasonable definition for big O in several variables is: $f(n,m) = O(g(n,m))$ if there exist $n_0,m_0,C>0$ such that $f(n,m) \leq Cg(n,m)$ for all $n \geq n_0$ and $m \geq m_0$. Now you can answer your own question. As a hint, note that $\log(2n+m) \leq \log(2n+2m) = \log 2 + \log(n+m)$.

1

For $a_n$ you use correct definition i.e. $a_n \in O(n^\alpha)$: $\exists C>0, \exists N_1 \in \mathbb{N}, \forall n>N_1, |a_n| \leqslant C n^\alpha$. For little-$o$ for $b_n \in o(n^\beta)$ let's use following definition : $\exists \varepsilon_n, \lim\limits_{n \to \infty}\varepsilon_n=0$ and $\exists N_2 \in \mathbb{N}$ such that $\forall n>N_2,... 1 You can just view$\mathcal{O}(n^2)$as an anonymous function drawn from the underlying class. The statement means: The running time of the algorithm is at most quadratic in the input length$n\$. I do not think there is anything controversial or wrong here.

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