Generic Form
The master theorem concerns recurrence relations of the form:
In the application to the analysis of a recursive algorithm, the constants and function take on the following significance:
- n is the size of the problem.
- a is the number of subproblems in the recursion.
- n/b is the size of each subproblem. (Here it is assumed that all subproblems are essentially the same size.)
- f (n) is the cost of the work done outside the recursive calls, which includes the cost of dividing the problem and the cost of merging the solutions to the subproblems.
It is possible to determine an asymptotic tight bound in these three cases:
Read more about this topic: Master Theorem
Famous quotes containing the words generic and/or form:
““Mother” has always been a generic term synonymous with love, devotion, and sacrifice. There’s always been something mystical and reverent about them. They’re the Walter Cronkites of the human race . . . infallible, virtuous, without flaws and conceived without original sin, with no room for ambivalence.”
—Erma Bombeck (20th century)
“Quite generally, the familiar, just because it is familiar, is not cognitively understood. The commonest way in which we deceive either ourselves or others about understanding is by assuming something as familiar, and accepting it on that account; with all its pros and cons, such knowing never gets anywhere, and it knows not why.... The analysis of an idea, as it used to be carried out, was, in fact, nothing else than ridding it of the form in which it had become familiar.”
—Georg Wilhelm Friedrich Hegel (1770–1831)