Shortcut Rule
If the time-complexity of the function is in the form
Then the Big-Oh of the time-complexity is thus:
- If, then the time-complexity is
- If, then the time-complexity is
- If, then the time-complexity is
where represents the number of recursive calls at each level of recursion, represents by what factor smaller the input is for the next level of recursion (i.e. the number of pieces you divide the problem into), and represents the work the function does independent of any recursion (e.g. partitioning, recombining) at each level of recursion.
Read more about this topic: Recursive Call, Time-efficiency of Recursive Algorithms
Famous quotes containing the word rule:
“Until the Women’s Movement, it was commonplace to be told by an editor that he’d like to publish more of my poems, but he’d already published one by a woman that month ... this attitude was the rule rather than the exception, until the mid-sixties. Highest compliment was to be told, “You write like a man.””
—Maxine Kumin (b. 1925)