CODEWITHSUNDEEP
algorithmmath
JiaHao Xu
JiaHao Xu

Reputation: 2748

Can't understand the proof of worst time complexity in Algorithms P146

On page 146 in Algorithms Fourth Edition, a proof of the worst time complexity of quick-union algorithm is given. It says

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).

I can't understand why 1 + log(i) = log(i + i).

Upvotes: 2

Views: 60

Answers (1)

OmG
OmG

Reputation: 18838

Because log(i + i) = log(2i) = log(2) + log(i) and as log(2) = 1, we can say log(i + i) = 1 + log(i).

Upvotes: 8

Related Questions