Data Structures and Algorithms MCQ - Performance Analysis of Algorithms and Recurrences

The best algorithm is we can solve in linear time using right to left pass.

a₁, a₂ .....................a_n
b₁, b₂ .....................b_n
In order to find out the largest span, check the sums of
a_i +............a_j and b_i +..............b_j at each step.
If a₁ + a₂ = b₁ + b₂ go on, check a₁ + a₂ + a₃ and b₁ + b₂ + b₃.
If not, then check a₂ + a₃ and b₂ + b₃
Similarly a check is done at each of the n places during traversal. A separate variable has to be kept that contains the maximum span observed hitherto
Hence fastest algorithm computes with (~) (n) time and space.

From the list of given n numbers [say n is even], Pick up first two elements, compare them
assign Current – min = min of two numbers
Current – max = max of two numbers
From the remaining n – 2 numbers, take pairs wise and follow this process given below.

1. Compare two elements
Assign min = min of two numbers
max = max of two numbers

2. Compare min and current – min
Assign current – min
= min{current– min,min}

3. Compare max and current – max
Assign current – max
= max{current – max, max}

Repeat above procedure for all the remaining pairs of numbers. We can observe that each of pair requires 3 comparisons
1. for finding min and max
2. For updating current – min
3. for updating current – max
But for initial pair we need only one comparison not 3.
∴ Total number of comparisons

Here n =100, so number of comparisons = 148.

Given: n numbers
To find: Tightest upper bound on number of swaps required to sort n numbers using selection sort.
Analysis: In selection sort, in the unsorted part of the array, we find the minimum element and swap it with the value placed at the index where the unsorted array starts.
Hence, for each element to put it in its sorted position, we will do some swaps. In each itenation, when we find the minimum and place it in its sorted position, we do only one swap.
There are n such iterations, since maximum number of positions to sort is n.
Hence, there are n.O(1) swaps
⇒ O(n) swaps.
∴ The solution is (B)