はじめに

証明に入る前に、そもそも、計算量が $O(max(n,m))$ や $O(n+m)$ で表されるような具体例はあるのでしょうか。

Python で書かれた以下の関数 $f(x)$ を見てみてください。関数 $f(x)$ は正整数 $x$ が与えられたときに ${\displaystyle \sum _{1\le k\le x}k}$ を返す関数です。例えば $x=4$ のときは $f(4)=1+2+3+4=10$ となるので $10$ を返します。

def f(x):
    total = 0
    for k in range(1, x + 1):
        total += k
    return total

これから、標準入力として $2$ つの正整数 $n,m$ が与えられるとします。関数 $f(x)$ を使った次の $2$ つのプログラム $P,Q$ を考えてみると、（直感的には）プログラム $P$ の計算量は $O(max(n,m))$ 、プログラム $Q$ の計算量は $O(n+m)$ と見積もれます。

# 関数 f(x)
def f(x):
    total = 0
    for k in range(1, x + 1):
        total += k
    return total

# 標準入力
n = int(input())
m = int(input())

if n > m:
    print(f(n))
else:
    print(f(m))

# 関数 f(x)
def f(x):
    total = 0
    for k in range(1, x + 1):
        total += k
    return total

# 標準入力
n = int(input())
m = int(input())

print(f(n))
print(f(m))

証明

$O(max(n,m))$ を $O(n+m)$ と書き表しても良いことをこれから証明します。
$n>m$ と $n\le m$ の場合分けで示します。

• $n>m$ のとき
  • $max(n,m)=n$ となるので、$O(max(n,m))=O(n)$ が言えます。
  • $m<n$ の両辺に正の定数 $k$ を掛けると、$km<kn$ となります。両辺に $kn$ を加えると、$kn+km<kn+kn=2kn\le 3kn$ すなわち、$k(n+m)\le 3kn$ が成り立ちます。 $O$ 記法の定義より、$O(k(n+m))=O(n+m),O(3kn)=O(n)$ なので、$O(n+m)=O(n)$ が言えます。

以上より、$n>m$ のときは $O(max(n,m))=O(n+m)$ が成り立ちます。

• $n\le m$ のとき
  • $max(n,m)=m$ となるので、$O(max(n,m))=O(m)$ が言えます。
  • $n\le m$ の両辺に正の定数 $k$ を掛けると、$kn\le km$ となります。両辺に $km$ を加えると $kn+km\le km+km=2km$ すなわち、$k(n+m)\le 2km$ が成り立ちます。 $O$ 記法の定義より、$O(k(n+m))=O(n+m),O(2km)=O(m)$ なので、$O(n+m)=O(m)$ が言えます。

以上より、$n\le m$ のときは $O(max(n,m))=O(n+m)$ が成り立ちます。

したがって、$O(max(n,m))$ を $O(n+m)$ と書き表しても良いことが分かります。