Recursive Call - Time-efficiency of Recursive Algorithms - Shortcut Rule

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:

    “Nothing requires a greater effort of thought than arguments to justify the rule of non-thought.”
    —Milan Kundera (b. 1929)