Question

What is the largest size n of a problem that can solve in 1 second, assuming that the algorithm to solve the problem takes sqrt(n) microseconds? (sqrt stands for square root)

		1
		10^(6)
		10^(12)
		10^(3)

How does the array arr = [8, 5, 3, 6, 10] look like after the second iteration (when j = 3) of the j loop on line 1 of the give pseudocode below?

insertion_sort.PNG

1 for j
2 do
3 // Insert A[j] into the sorted

// sequence A[1..j - 1] –1

5 while i > 0 and A[i] > key do

7. ii–1
8 A[i + 1] key

		[5, 8, 3, 6, 10]
		[3, 5, 5, 6, 10]
		[8, 5, 3, 6, 10]
		[3, 5, 8, 6, 10]

Answer 1

Answer 1 : The largest size n of a problem that can solve in 1 second is 10^(12) .

Explanation :

Given : Time taken by the algorithm to solve the problem = sqrt(n) microseconds

To find : Largest size n of a problem that can solve in 1 second

Solution :

For n , the time = sqrt(n) microsecond - ( i )

So, for 1 second time, the size will be given as

time = 1 second

= microseconds

time  = microseconds

Comparing with equation ( i ) , we get

n =

i.e n = 10^12

Answer 2 : The array arr = [8, 5, 3, 6, 10] after the second iteration (when j = 3) of the j loop will look like [3, 5, 8, 6, 10].

Explanation :

I am assuming index starts at 1 here.

The given array is [8, 5, 3, 6, 10].

As per algorithm ,

Step 1 : For j = 1 ,

Key = A[ j ] = 8

i = j - 1 = 1 - 1 = 0

Inner while loop does not run and ends at the start because i = 0 which is invalid.

A [ i + 1 ] = key      =        A [ 1 ] = 8

Step 2 : For j = 2 ,

Key = A[ j ] = 5

i = j - 1 = 2 - 1 = 1

For (First inner iteration) ,

Condition (i > 0 and A[ i ] > key ) = 1>0 and A[ 1 ] > 5 = true and 8 > 5 = true and true = true

Therefore, A[ 2 ] = 8 and i = i – 1 = 1 – 1 = 0

Then while loop ends since i = 0 ( Second inner iteration)

A [ i + 1 ] = key      =        A [ 2 ] = 8

  [5, 8, 3, 6, 10].

Step 3 : For j = 3 ,

Key = A[ j ] = 3

i = j - 1 = 3 - 1 = 2

For (First inner iteration )

Condition (i > 0 and A[ i ] > key )          = 2>0 and A[ 2 ] > 3 = true and 8 > 3 = true and true = true

Therefore, A[ 3 ] = A [ 2 ]       A [ 3 ] = 8 and i = i – 1 = 2 – 1 = 1

The array will be   [5, 8, 8, 6, 10].

For (Second inner iteration)

Condition (i > 0 and A[ i ] > key )              = 1>0 and A[ 1 ] > 3 = true and 5 > 3 = true and true = true

Therefore, A[ 2 ] = A [ 1 ]       A [ 2 ] = 5 and i = i – 1 = 1 – 1 = 0

The array will be   [5, 5, 8, 6, 10].

For (Third inner iteration)

While loop ends since i = 0 which is invalid.

A [ i + 1 ] = key      =        A [ 1 ] = 3

The array will be   [3, 5, 8, 6, 10].