3 Years
Discussion Span
Last Post by amina.bm

n is typically represented as a collection of items being processed by the algorithm because that's easy to visualize. For example, if you have an array of 10 items, replace n with 10 for a specific calculation.


Ok so that's the input instance size.I also have one more doubt.How can i write a** recursive formula** for any code?

Edited by inspire_all


How can i write a recursive formula for a code and then solve it by substitution/master method ?

Edited by inspire_all



To be able to use Master Theorem, one has to check first that the initial problem satisfying the following condition:

Given problem p of size n, it may be divided into m sub-problems of equal size; inferior strictly to n, such that m>=1.

If so, p can be stated as follows:

p(n)= a p(n/b)+cn^k. k>=0, n>=1, c>=1, b>=1 such that,

a: the number of sub-problems.

n/b: sub-problems size.

cn^k: the cost of dividing p and combining then the sub-problems set.

and we have then three cases:

  1. a>b^k so p belongs to O(n^(log_b(a)).

  2. a=b^k so p belongs to O(n^klog(n)).

  3. a<b^k so p belongs to O(n^k).


This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.