All Science Fair Projects

Science Fair Project Encyclopedia for Schools!

Search Browse Forum Coach Links Editor Help Tell-a-Friend Encyclopedia Dictionary

Science Fair Project Encyclopedia

Science Fair Project Encyclopedia Contents Page

Master theorem

In the analysis of algorithms, the master theorem, which is a specific case of the Akra-Bazzi theorem, provides a cookbook solution in asymptotic terms for recurrence relations of types that occur in practice. Suppose given such a relation of the form

$T(n) = a T\left(\frac{n}{b}\right) + f(n)\,$

where

$a \ge 1\,$

and

$b > 1\,$

are taken as constants and

$\frac{n}{b}\,$

is interpreted as either

$\left\lfloor \frac{n}{b} \right\rfloor\,$ (the floor function)

or as

$\left\lceil \frac{n}{b} \right\rceil\,$ (the ceiling function)

of the ratio

$\frac{n}{b}.$

Then we may bound the relation

$T(n)\,$

according to one of the following three cases:

Case 1: If

$f(n) \in O\left( n^{\log_b a - \varepsilon} \right)$ (the big-O notation)

for some constant

$\varepsilon > 0\,$

then

$T(n) \in \Theta\left( n^{\log_b a} \right).\,$

Case 2: If

$f(n) \in \Theta\left( n^{\log_b a} \right)\,$

then

$T(n) \in \Theta\left( n^{\log_b a} \log(n)\right).\,$

Case 3: If

$f(n) \in \Omega\left( n^{\log_b a + \varepsilon} \right)$

for some constant

$\varepsilon > 0$

and if

$a f\left( \frac{n}{b} \right) \le c f(n)$

for some constant

c < 1

and for some sufficiently large $n$ , then $T(n) \in \Theta(f(n)).$

See also MacMahon's master theorem .

Science Fair Project Encyclopedia Contents Page

10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details

Science kits, science lessons, science toys, maths toys, hobby kits, science games and books - these are some of many products that can help give your kid an edge in their science fair projects, and develop a tremendous interest in the study of science. When shopping for a science kit or other supplies, make sure that you carefully review the features and quality of the products. Compare prices by going to several online stores. Read product reviews online or refer to magazines.

Start by looking for your science kit review or science toy review. Compare prices but remember, Price $ is not everything. Quality does matter.

Science Fair Coach
What do science fair judges look out for?

ScienceHound
Science Fair Projects for students of all ages

All Science Fair Projects.com Site
All Science Fair Projects Homepage

Search | Browse | Links | From-our-Editor | Books | Help | Contact | Privacy | Disclaimer | Copyright Notice