Inadmissible Equations
The following equations cannot be solved using the master theorem:
-
- a is not a constant
-
- non-polynomial difference between f(n) and (see below)
-
- a<1 cannot have less than one sub problem
-
- f(n) is not positive
-
- case 3 but regularity violation.
In the second inadmissible example above, the difference between and can be expressed with the ratio . It is clear that for any constant . Therefore, the difference is not polynomial and the Master Theorem does not apply.
Read more about this topic: Master Theorem
Famous quotes containing the word inadmissible:
“The farmer stands well on the world. Plain in manners as in dress, he would not shine in palaces; he is absolutely unknown and inadmissible therein; living or dying, he never shall be heard of in them; yet the drawing-room heroes put down beside him would shrivel in his presence; he solid and unexpressive, they expressed to gold-leaf.”
—Ralph Waldo Emerson (1803–1882)