Ì Exam ple 7.1.1: Given P n a
a n a n
a n
m
m
( ) =
+
+
+ +
0
1
2
2
L
. Show
that
P n O n
m
( )
( ).
=
Solu tion
Let b
a b
a
b
a
m
m
0
0
1
1
=
=
=
| |,
| |,
| |.
KK
Then for n ≥1,
P n b b n b n
b n
b
n
b
n
b n
m
m
m
m
m
m
( ) ≤ +
+
+
+
=
+
+
+






−
0
1
2
2
0
1
1
LL
LL
≤
+ +
+
=
(
)
b b
b n
Mn
m
m
m
0
1
LL
where
M
a
a
a m
=
+ +
+
| | | |
| |.
0
1 LL
There fore
P n O n
m
( )
( ).
=
Ì Exam ple 7.1.2: Find the order of the following polynomials:
(a) f n
n
n
1
3
5
3 1
( ) =
+ +
(b) f n n
n
2
5
2
400
( ) =
−
Solu tion
(a) ( ( ))
( ).
f n
O n
1
3
=
(b) f n O n
2
5
( )
( ).
=
7.2 POLYNOMIAL-TIME ALGORITHMS
A polynomial-time algorithm is an algorithm whose execution time is either
given by a polynomial on the size of the input, or can be bounded by such a
polynomial. Problems which can be solved by a polynomial-time algorithm
are called “tractable” problems. As an example, most algorithms on arrays can
use the array size, n, as the input size. In order to find the largest element in any
array requires a single pass through the array, so the algorithm which does this
is of O(n), or it is a “linear time” algorithm.
Sorting algorithms take O(n log n) or O(n
2 ) time. Bubble sort takes linear
time in the least case, but O(n
2 ) time in the average and worst cases. Heapsort
takes O(n log n) time in all cases. Quicksort takes O(n log n) time on average,
but O(n
2 ) time in the worst case.
As far as O(n log n) is concerned, it must be noted that the base of the
logarithms is irrelevant, as the difference is a constant factor, which is ignored.
All programming tasks we know have polynomial solutions. It is not due
to the reason that all practical problems have polynomial-time solutions.
236
Theory of Automata, Formal Languages and Computation