13. Mention the time complexities of a bubble sort in (a) best case
(b) average case and (c) worst case?
(a) Best case: O(n)
(b) Average case: O n
( )
2
(c) Worst case: O(n
2 ).
14. Mention the time complexities of Quicksort algorithm in (a) best case
(b) average case and (c) worst case.
(a) Best case: O n
n
( log )
(b) Average case: O n
n
( log )
(c) Worst case: O n
( )
2
15. Discuss the feasibility of the following complexities:
(a) O
n
( )
2
(b) O n
( )
3
(c) O n
( )
2 .
(a) O
n
( )
2 → rarely feasible
(b) O n
( )
3
→ less often feasible
(c) O n
( )
2
→ sometimes feasible
16. Discuss the feasibility of the following complexities.
(a) O n
n
( log ) (b) O n
( ) (c) O( )
1
(a) O n
n
( log ) → feasible
(b) O n
( ) → feasible
(c) O( )
1 → feasible
17. What is a non-deterministic Polynomial Time algorithm?
It is the one that can be executed in polynomial time on a
non-deterministic machine.
18. What are the view points of a non-deterministic computation?
(a) When a choice point is reached, an infallible oracle can be
consulted to determine the right option.
(b) When a choice point is reached, all choices are made and
computation can proceed simultaneously.
19. Name some of the intractable problems.
(a) Integer Bin packing
(b) Knapsack problem
(c) Travelling Salesman Problem
20. What is ‘integer bin packing’ problem?
Assume we are given a set of n integers. Our task is to arrange these
integers into two piles or bins, so that the sum of the integers in one pile
is equal to the sum of the integers in the other pile.
21. What is Boolean satisfiability?
A Boolean formula is satisfiable if some assignment of 0s and 1s to
the variables makes the formula evaluate to 1.
Complexity Theory
243