Let
,
et
be functions from
to
Let us give some examples.
We have the following properties.
In practice
is replaced by
in each of the expressions
,
and
.
Hence, the following
![$\displaystyle f(n) = h(n) + {\Theta}(g(n))$](img98.png) |
(11) |
means
![$\displaystyle f(n) - h(n) \in {\Theta}(g(n)).$](img99.png) |
(12) |
Let us give another fundamental example.
Let
be a (univariate) polynomial with degree
.
Let
be its leading coefficient and assume
.
Then we have
- if
then
,
- if
then
,
- if
then
.
Exercise: Prove the following
![$\displaystyle {\Sigma}_{k=1}^{k=n} \, {k} \ \in \ {\Theta}(n^2).$](img113.png) |
(13) |
Marc Moreno Maza
2008-01-07