Virtual Labs

1. What will be the space complexity of the algorithm?

a: O(N) Explanation

Explanation

b: O(2^N) Explanation

Explanation

c: O(1) Explanation

Explanation

d: O(N^2) Explanation

Explanation

2. Consider the following array:
A = [8, 7, -2, 4, 1, 100, 0, -1]
Which of the following subarray pairs are merged with each other during one of the merge operations (assume ascending order sort)?

a: [-2, 4] and [1, 100] Explanation

Explanation

b: [7, 8] and [-2, 4] Explanation

Explanation

c: [8, 7] and [-2, 4] Explanation

Explanation

d: [1, 4] and [0, 100] Explanation

Explanation

3. Why is the complexity of the algorithm N log (N)?

a: N for the complexity of dividing the array into subarrays and log (N) for the number of times the division operation occurs. Explanation

Explanation

b: N for the complexity of merging subarrays and log (N) for the number of times the merge operation occurs. Explanation

Explanation

c: N for the number of times the division operation occurs and log (N) for the complexity of dividing the array into subarrays. Explanation

Explanation

d: N for the number of times the merge operation occurs and log (N) for the complexity of merging subarrays. Explanation

Explanation

4. Consider the following array:
A = [0, -1, 100, 110, 1, 5]
Which of the following represents the steps in sorting the above array?

a: [0, -1, 100, 110, 1, 5] → [0, -1, 100], [110, 1, 5] → [0], [-1, 100], [110], [1, 5] → [0], [-1], [100], [110], [1], [5] → [-1, 0], [100], [1, 110], [5] → [-1, 0, 100], [1, 5, 110] → [-1, 0, 1, 5, 100, 110] Explanation

Explanation

b: [0, -1, 100, 110, 1, 5] → [0, -1, 100], [110, 1, 5] → [0, -1], [100], [110, 1], [5] → [0], [-1], [100], [110], [1], [5] → [0], [-1, 100], [110], [1, 5] → [-1, 0, 100], [1, 5, 110] → [-1, 0, 1, 5, 100, 110] Explanation

Explanation

c: [0, -1, 100, 110, 1, 5] → [0, -1, 100], [110, 1, 5] → [0], [-1, 100], [110], [1, 5] → [0], [-1], [100], [110], [1], [5] → [0], [-1, 100], [110], [1, 5] → [-1, 0, 100], [1, 5, 110] → [-1, 0, 1, 5, 100, 110] Explanation

Explanation

d: [0, -1, 100, 110, 1, 5] → [0, -1, 100], [110, 1, 5] → [0], [-1, 100], [110, 1], [5] → [0], [-1], [100], [110], [1], [5] → [0], [-1, 100], [1, 110], [5] → [-1, 0, 100], [1, 5, 110] → [-1, 0, 1, 5, 100, 110] Explanation

Explanation

Merge Sort