この再発の解決策は何ですか？
T(n) = T(n/1000) + T(999n/1000) + cn.
レベルごとに行われる作業は cn になり、ツリーの高さは 1000/999 を底とする log n になるため、O(n log n) だと思いますが、その理由が有効かどうかはわかりません。あれは正しいですか？
この再発の解決策は何ですか？
T(n) = T(n/1000) + T(999n/1000) + cn.
レベルごとに行われる作業は cn になり、ツリーの高さは 1000/999 を底とする log n になるため、O(n log n) だと思いますが、その理由が有効かどうかはわかりません。あれは正しいですか？