- Option : B
- Explanation :

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

You must be logged in to post a comment.

- Option : C
- Explanation :

a_{1}, a_{2}.....................a_{n}

b_{1}, b_{2}.....................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_{1}+ a_{2}= b_{1}+ b_{2}go on, check a_{1}+ a_{2}+ a_{3}and b_{1}+ b_{2}+ b_{3}.

If not, then check a_{2}+ a_{3}and b_{2}+ b_{3}

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.

You must be logged in to post a comment.

You must be logged in to post a comment.

- 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.

You must be logged in to post a comment.

You must be logged in to post a comment.

- 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)

You must be logged in to post a comment.

You must be logged in to post a comment.

You must be logged in to post a comment.