DAA- Tutorial

What is the Complexity of BUILD_MAX_HEAP function?

• O(log n)

• O(n log n)

• O(n)

• None of the above

Heap_Increase_key operation is used for

• Increase the depth of the heap

• to insert a new node in the heap with given key.

• to increase the value of the given index with the new key value

• to remove the max value from the heap

What is the lower bound for comparison based sorting algorithms?

• nlogn

• n²

• logn

• n

What is the order of partition algorithm in quick sort?

• O(logn)

• O(nlogn)

• O(n)

• O(1)

Order the complexity function in ascending order of their complexity

a. n

b. log n

c. n²

d. n logn

• a, b, c, d

• c, d, a, b

• b, a, d, c

• d, c, b, a

Which sorting algorithm makes one swap per pass (possibly swapping an element with itself)?

• Selection Sort
• Bubble Sort
• Insertion Sort

Which sorting algorithm may make multiple swaps per pass?

• Bubble Sort
• Selection Sort
• Insertion Sort

Which sorting algorithm shifts elements instead of swapping elements if needed in each pass.

• Bubble Sort
• Selection Sort
• Insertion Sort

How many passes will both the selection and insertion sorts make?

• N
• N-1
• N+1
• (N+1)/2

The following lists represent 3 passes of a sorting algorithm. Which algorithm is being used to sort the list?
 
4    5    9    6    2    7
4    5    6    2    7    9 
4    5    2    6    7    9

• Bubble Sort
• Selection Sort
• Insertion Sort