1
$\begingroup$

The general formula for time complexity is $T(n) = aT(n/c) + bn^k$.

  • If $a> c^k$, the complexity is $O(n^{\log_c a})$.
  • If $a = c^k$, it is $O(n^k \log n)$.
  • If $a < c^k$, it is $O(n^k)$.

$a$ is the amount of times the recursive function is called, but what do $b$, $c$, and $k$ represent?

$\endgroup$
  • $\begingroup$ "The general formula for time complexity" -- there is no such thing. $\endgroup$ – Raphael Aug 28 '16 at 9:27
  • $\begingroup$ Have you looked at some applications? $\endgroup$ – Raphael Aug 28 '16 at 9:27
  • $\begingroup$ That "general formula" is for one very specific situation; usually for divide-and-conquer algorithms. It's useful in some practical situations, and in many exam questions, but it is most definitely not a "general formula for time complexity". $\endgroup$ – gnasher729 Aug 28 '16 at 18:31
3
$\begingroup$

That is not the general formula for time complexity. There is no "general formula for time complexity", any more than there is a "general formula for the answer."

Rather, the formula you give is a recurrence relation that can be used to compute the running time of certain divide-and-conquer–style recursive algorithms. Specifically, it corresponds to a recursive function which, when given an input of size $n$, makes $a$ recursive calls, each on inputs of size $n/c$. If you pretended that the recursive calls were "free" (i.e., that they returned their answer in one computation step), then the algorithm would take $bn^k$ steps.

$\endgroup$
2
$\begingroup$

The Master theorem applies to recurrences of a certain form; in algorithm analysis, usually such for running-time functions of divide & conquer algorithms. If you look at some examples, you'll note that the common scheme is that

  1. the input is divided into parts of size $n/c \pm 1$,
  2. the algorithm is executed recursively on $a$ of these parts, and
  3. the results of the recursive calls are then combined into the final result.

Now, steps 1 and 3 take some time, which the authors of that "general formula" of yours (which is anything but) assume to be of the form $bn^k$ (they probably mean $\Theta(n^k)$, or even $O(n^k)$, but simplify to this explicit function so the calculations work out more neatly).

See here for a longer explanation of the Master theorem with applications. There are some other questions on the Master theorem you may want to read through.

$\endgroup$
-1
$\begingroup$

I think you must mean solving recurrences of the form T(n) = aT(n/b) + f(n).

From the relations that you have written I understand that you must be trying to learn the Master Method for solving recurrences. This is used where a divide and conquer strategy is used by the algorithm to solve problems. The D&C strategy divides a given problem into specific parts in order to solve it effectively.

Here a implies the number of parts a single problem is divided into.

(n/b) is the size of each sub-problem and

f(n) is the cost of solving(combining and splitting) each sub problem.

More details of the master method can be understood from here as suggested earlier by Raphael

$\endgroup$
  • $\begingroup$ The OP clearly states which form of recurrences they want to know about. It's less general than the form you quote, but nevertheless you should try to answer the question as written. $\endgroup$ – Raphael Sep 4 '16 at 21:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.