SHORT QUESTIONS AND ANSWERS
1. What are the measures of Complexity Theory?
(a) Time (b) Space
2. What is meant by time complexity?
It is a measure of how long a computation takes to execute.
3. What is meant by space complexity?
It is a measure of how much storage is required for a computation.
4. How do you measure space complexity in a Turing machine?
It is the number of tape squares used.
5. How do you measure space complexity in a digital computer?
It is the number of bytes used in a digital computer which is a
measure of space complexity.
6. What are the different cases of complexities?
(a) averge case
(b) best case
(c) worst case.
7. What is order statistic?
In complexity theory, equations are subjected to extreme
simplifications.
If an algorithm takes exactly 50
5
5 56
3
2
n
n
n
+
− + machine cycles,
where ‘n’ is the size of the input, then we shall simplify this to O n
( ).
3
This is called “order statistic”.
8. Determine the order of the polynomials
(a) f n
n
n
1
3
10
6 1
( ) =
+ +
(b) f n n
n
2
5
2
2
( ) =
−
(a) f n O n
1
3
( )
( )
=
(b) f n O n
2
5
( )
( )
=
9. What is a Polynomial time algorithm?
An algorithm whose execution time is either given by a polynomial
on the size of the input or can be by bounded by such polynomial is a
polynomial time algorithm.
10. What are tractable problems?
Problems which can be solved by a polynomial time algorithm are
called tractable problems.
11. What do you mean by saying that an algorithm is an O(n) algorithm?
It means it is a linear time algorithm.
12. What are the time complexities of sorting algorithms?
O n
n
O n
( log )
( ).
or
2
242
Theory of Automata, Formal Languages and Computation