8. State some of the common time complexities.
9. Discuss the feasibility of the following complexicities
(a) O(1)
(b) O(log n)
(c) O(n)
(d) O(n log n)
(e) O(n
2 )
(f) O(n
3 )
(g) O(2
n )
(h) O
n
( )
2
2
10. What are heuristic algorithms?
11. Explain the following intractable problems
(a) Integer Bin packing
(b) TSP
12. What do you mean by Boolean satisfiablity?
13. What are P-class problems?
14. What are NP-class problems?
15. When are problems said to be NP-complete?
16. Give examples for
(a) class-P
(b) class-NP Problems.
EXERCISES
1. Prove the following
(a) n
n
2
100
+
log is O n
( )
2
(b) n! is O n
n
( )
(c) 3
n is O n
( !)
2. Given f n
n
n
( ) =
+
5
2
and g n O n
( )
( )
=
2 . Is the statement
f n g n O n
( )
( )
( )
−
=
valid?
3. Determine the order of the following polynomials
(a) f n
n
n
a ( ) =
+ −
100
3 1
2
(b) f n
n
n
n
b ( )
.
=
−
−
5
4
200
5
4
2
4. Discuss the feasibility of algorithms with following time complexities.
(a) O
n
(log ) (b) O n
n
( log ) (c) O n
( )
2
5. Discuss the feasibility of algorithms with following time complexities.
(a) O(n
3 ) (b) O
n
( )
2
(c) O n
( !)
6. Explain Boolean satisfiability with an example.
7. Verify whether the following formula
(
) (
)
x y
x y
∧ ∨ ∧
is Boolean satisfiable or not.
Complexity Theory
241