Sử dụng cây đệ quy đánh giá độ phức tạp

[Lag_Lac (Lag /Lác)]

Mình đang tìm hiểu về sử dụng cây đệ quy để đánh giá độ phức tạp và tìm đươc 1 ví dụ này, mình không hiểu khúc tại sao chiều cao của cây lại thỏa mãn n^(2-L) = O(1) và giải kiểu gì để ra L = O(loglogn). Ai đó làm ơn giải thích giúp mình với

[noname00 (HK boy)]

Mình có search thử n log log n thì thấy ở reply này có đề cập đến Shrinking by a Square Root và giải thích với số mũ 2 giảm dần:

What would cause an algorithm to have O(log log n) complexity?

[rogp10]

Rút căn bậc hai tức là chia đôi log: \log{\sqrt n} = \log(n^\frac{1}{2}) = \frac{1}{2}\log n
Mà chia đôi mãi tức là log tầng => log log.

Số node tầng dưới gấp \sqrt n lần tầng trên nhưng khối lượng mỗi node cũng giảm đi \sqrt n lần.