overall complexity of additive algorithm

Question

Assume, for some fixed integer $n$ the computational algorithm consists of two consecutive parts. Part 1 has computational complexity of $O(n_{1})$ and Part 2 has complexity of $O(n_{2})$, and $n_{1} + n_{2} = n$.

What is the overall complexity of the whole algorithm? Is it $O(n)$?

Answer 1

The combined complexity of the algorithm is indeed $O(n_1+n_2)$. If $f_1(n),f_2(n)$ represent the worst case time of the first and second part of the algorithm for an input of size $n$ and $f_1(n)\in O(n_1(n)),f_2(n)\in O(n_2(n))$, then we have for some $M_1,M_2,n_{01},n_{02}\in\Bbb N$,$$\begin{align*}f_1(n)&\le M_1n_1(n)\forall n\ge n_{01}\\f_2(n)&\le M_2n_2(n)\forall n\ge n_{02}\\f_1(n)+f_2(n)&\le M_1n_1(n)+M_2n_2(n)\\&\le\max\{M_1,M_2\}(n_1(n)+n_2(n))~~\forall n\ge\max\{n_{01},n_{02}\}\end{align*}$$So $f_1(n)+f_2(n)\in O(n_1+n_2)$.

---

Note that we may be able to provide tighter bound on $f_1+f_2$ in case $n_1\in o(n_2)$ or $n_2\in o(n_1)$. In the former case, $f_1+f_2\in O(n_2)$ and similarly for the latter case. For example, if $n_1(n)=n^3,n_2(n)=n^4$ then $f_1(n)+f_2(n)\in O(n^4).$

This simplification is not possible when $f_1,f_2$ depend on different variables. Say $f_1$ depends on the number of rows $r$ of an inputed two dimensional array as $f_1(r)\in O(r^3)$, and let $f_2$ depend on its number of columns $c$ as $f_2(c)\in O(c^4)$. Then $f_1+f_2\in O(r^3+c^4)$ can't be simplified to $O(c^4)$.

Answer 2

Expressing complexity of each part

In big O notation $O(n)$ means that the complexity is a function of $n$ with smaller terms omitted.

Suppose the time complexity for part 1 has a function $f(n_1) = an_1+[\text{smaller terms}]$ such that $\lim_{n_1 \to \infty} \frac{f(n_1)}{n_1} = a$

Likewise suppose the time complexity for part 2 has a function $f(n_2) = bn_2+[\text{smaller terms}]$ such that $\lim_{n_2 \to \infty} \frac{f(n_2)}{n_2} = b$

Expressing complexity of combined parts

The time complexity for part 1 and 2 is the sum of their complexities, i.e. $f(n_1)+f(n_2)$.

With your constraint we know that $n_2=n-n_1$

The complexity is $f(n_1)+f(n-n_1)$.

Proving the complexity of combined parts

Consider the limit $\lim_{n \to \infty} \frac{f(n_1)+f(n-n_1)}{n}$. If this is finite and non-zero then the complexity is $O(n)$.

Expand this out

$\lim_{n \to \infty} \frac{an_1+b(n-n_1)+\text{[smaller terms]}}{n}$

We know that the smaller terms vanish in the limit so this gives

$\lim_{n \to \infty} b+\frac{(a-b)n_1}{n}$

Since ${0\leq n_1 \leq n}$ then $0 \leq \lim_{n\to \infty}\frac{n_1}{n} \leq 1$

Therefore $\lim_{n \to \infty} b+\frac{(a-b)n_1}{n}$ is finite and non zero because $a\neq 0$