1. For the bubble sort algorithm, what is the time complexity of the best/worst case?
(assume that the computation stops as soon as no more swaps in one pass)

best case: O(n) worst case: O(n*n)

best case: O(n) worst case: O(n*log(n))

best case: O(n*log(n)) worst case: O(n*log(n))

best case: O(n*log(n)) worst case: O(n*n)

best case: O(n) worst case: O(n*n)

2. For the quick sort algorithm, what is the time complexity of the best/worst case?

best case: O(n) worst case: O(n*n)

best case: O(n) worst case: O(n*log(n))

best case: O(n*log(n)) worst case: O(n*log(n))

best case: O(n*log(n)) worst case: O(n*n)

best case: O(n*log(n)) worst case: O(n*n)

3. In an arbitrary tree ( not a search tree) of order M. Its size is N, and its height is K.
The computation time needed to find a data item on T is

O(K*K)

O(M*M)

O(N)

O(K)

O(N)

4. Which of the following belongs to the algorithm paradigm?

Minimum & Maximum problem

Knapsack problem

Selection problem

Merge sort

Quick sort.

Knapsack problem

5. If f,t: N→ R+, then t (n) Ω (f (n)), iff f(n) O (t (n)) is known as

Limit rule

Rule of inference

Duality rule

Rule of consequences

6. The time taken by NP-class sorting algorithm is

O(1)

O(log n)

O(n2)

O(n)

O(n)

7. Find the odd one out from the following categories of algorithms.

TVSP

N-Queens

15-Puzzle

Bin-Packing.

Bin-Packing.

8. The time complexity of binary search in best, worst cases for an array of size N is

N, N2

1, Log N

Log N, N2

1, N log N

1, Log N

9. Which of following algorithm scans the list by swapping the entries whenever pair
of adjacent keys are out of desired order?

Insertion sort

Quick sort

Shell sort

Bubble sort

Bubble sort

10. The mathematical definition for Omega can be defined as, provided f,g:NR+ and c is
a positive constant and n > n0,