1. This problem explores how, when using a faster computer, thespeedup is affect

Question

1.                 This problem explores how, when using a faster computer, thespeedup is affected by the algorithm's complexity. Suppose we cansolve a problem size nin time t on aparticular computer. Now we are given a computer 16 times faster.In the same time t,approximately what size problem can you solve with the followingcomplexities: (n), (n2) ,(2n) ? Show anywork you need to do the problem.

(a) (n)

           (b) (n2)

         (c) (2n).

2.                 Suppose we have an array A[1 .. n] of integers, such that A[i] isthe maximum value of A.

           A[0] < A[1] < A[2] < . . . < A[i] > A[i+1] > A[i+2] . . . A[n-1] > A[n]

Describe an algorithm to find the maximum element of A in timefaster than(n)

Explanation / Answer

  min := 1;max := N; {array size: var A : array [1..N] of integer}repeatmid := (min + max) div 2;if x > A[mid] thenmin := mid + 1elsemax := mid - 1;until (A[mid] = x) or (min > max);

 where x is maximum value present in the Array A.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.