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

>>>>>>>>Performance Analysis of Algorithms and Recurrences

• Option : B
• Explanation :
The best algorithm is we can solve in linear time using right to left pass.

• Option : C
• Explanation :
a1, a2 .....................an
b1, b2 .....................bn
In order to find out the largest span, check the sums of
ai +............aj and bi +..............bj at each step.
If a1 + a2 = b1 + b2 go on, check a1 + a2 + a3 and b1 + b2 + b3.
If not, then check a2 + a3 and b2 + b3
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.

• Option : D
• Explanation :
Radix sort is counting based sorting technical the time complexity is Q(n).

• Option : A
• Explanation :
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.

• Option : B
• Explanation :
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)