I know many algorithms that can be analyzed using master theorem, but the only algorithm I know where the time is dominated by the leaves is fast matrix multiplication.

Are there other recursive algorithms (not necessarily master-theorem-style -- can be akra bazzi/something similar) where the time is dominated by the leaves? Would be grateful for any references.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.