How complexity of algorithms are compared

Question

I have two algorithms one with complexity $O(100)$ and the other with complexity $O(270)$. Can anyone give me a clear explanation of what exactly this means and how they are compared?

Answer 1

Let $k>0$. If $T_A(n)$ is the cost of the algorithm $A$ for an input of size $n$, saying that $A$ is $O(k)$ is saying that $T_A(n)$ is $O(k)$, which means that there are constants $m_A$ and $M_A$ such that $T_A(n)\le kM_A$ whenever $n\ge m_A$.

Suppose that $A$ is $O(k)$, and let

$$M=\max\{kM_A,T_A(0),T_A(1),\ldots,T_A(m_A-1)\}\;;$$

Clearly $T_A(n)\le M$ for $0\le n<m_A$, and for $n\ge m_A$ we know that

$$T_A(n)\le kM_A\le M\;,$$

so $T_A(n)\le M$ for all $n\in\Bbb N$. Conversely, if $T_A(n)\le M$ for all $n\in\Bbb N$, let $m_A=0$ and $M_A=\frac{M}k$; then it’s certainly true that

$$T_A(n)\le M=kM_A$$

for all $n\ge 0=m_A$ and hence that $A$ is $O(k)$. Thus, $A$ is $O(k)$ if and only if there is an $M$ such that $T_A(n)\le M$ for all $n\in\Bbb N$, i.e., if and only if $T_A$ is a bounded function.

Thus, the algorithms $A$ that are $O(100)$ are those for which the function $T_A$ is bounded, and so are the algorithms that are $O(270)$: these are both simply the class of algorithms whose costs are bounded by some amount independent of the size of the input.

(You didn’t specify whether you’re interested in time complexity, space complexity, or something else, but whatever you’re measuring, it’s some kind of cost: execution time, space required, etc.)