algorithm - 无法理解算法 P146 中最坏时间复杂度的证明

Question

Algorithms Fourth Edition第146页给出了quick-union算法最差时间复杂度的证明。它说

Let's assume the height of a tree which has i nodes has the maximum height of log(i).

Given i + j = k, i <= j, when the tree of i and j nodes are unioned, the height of the tree = 1 + log(i) = log(i + i) <= log(i + j) = log(k).

我不明白为什么 1 + log(i) = log(i + i)。

Answer 1

因为 log(i + i) = log(2i) = log(2) + log(i) 并且 log(2) = 1，我们可以说 log(i + i) = 1 + log(i)。