【計算量】なぜ O(max(n, m)) を O(n + m) と書けるのか？その理由を解説！

はじめに

証明に入る前に、そもそも、計算量が $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$ を返します。

関数 $f(x)$

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)$ と見積もれます。

プログラム $P$

# 関数 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))

プログラム $Q$

# 関数 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 \gt m$ と $n \le m$ の場合分けで示します。

• $n \gt m$ のとき
  • $\max(n, m) = n$ となるので、$O(\max(n, m)) = O(n)$ が言えます。
  • $m \lt n$ の両辺に正の定数 $k$ を掛けると、$km \lt kn$ となります。両辺に $kn$ を加えると、$kn + km \lt 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 \gt 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)$ と書き表しても良いことが分かります。