Each of the following three algorithms reverses an array. For each algorithm, gi

Question

Each of the following three algorithms reverses an array. For each algorithm, give a function that describes the number of steps the algorithm will take on an input of N elements in the worst case. You can be off by up to a constant multiplicative factor, or off by an additive constant. For example, if the algorithm were linear search on an ordered array, N would be a correct answer, while the answer of 2N+3 would still be acceptable (if a bit out of nowhere). Assume the first element of the array is element 1 (as opposed to 0).

1. REVERSE1(A): //Reverse the order of elements in an array

for each index i from 1 to floor(N/2):

swap element i with element N-i+1

return A

2. REVERSE2(A): // Reverse the order of elements in an array

for i = 1 to N-1:

for j = 1 to N-i:

swap element j with element j+1

return A

3. REVERSE3(A): // Reverse the order of elements in an array

// P is an array; assume generating next permutation takes 1 step.

for every possible permutation P of A:

for index i = 1 to N:

if P[i] is not equal to A[N-i+1]:

continue to the next permutation

// All elements matched in proper places

return P

4. Using your functions (even if you approximated), calculate the number of steps taken for each of these algorithms when N=100. (Google can act as a pretty good calculator if your scientific calculator isn’t up to the job.) If you approximated your answers to problems 1-3, judge whether your approximations affected these numbers enough to change the ranking of the algorithms by worst case running time.

Explanation / Answer

1. REVERSE1(A): //Reverse the order of elements in an array

for each index i from 1 to floor(N/2):

swap element i with element N-i+1

return A

This function goes from 1 to N/2 and in each iteration it do constant operations to swap element

So this will take N/2*2 times (N/2 times loop run and 2 operation per iteration) = N

2.

REVERSE2(A): // Reverse the order of elements in an array

for i = 1 to N-1:

for j = 1 to N-i:

swap element j with element j+1

return A

Outer loop runs for N-1 times and each outer loop run invoke a inner loop.

Inner loop run for N-i times and do constant operation (say 2)

So number of steps would be 2(N-1) + 2(N -2) + 2(N-3) + 2(N-4) + .....+2(1) = 2N^2 - (N^2 -N) = N^2 + N

3.

REVERSE3(A): // Reverse the order of elements in an array

// P is an array; assume generating next permutation takes 1 step.

for every possible permutation P of A:

for index i = 1 to N:

if P[i] is not equal to A[N-i+1]:

continue to the next permutation

// All elements matched in proper places

return P

There are N! permutation of A and in each permutation, in worst case there can be N/2 runs of loop (each element matching permutation also make one more element match) when N/2th element dosn't match.

So this gives (N+1)!/2 steps.

4.
N = 100

Problem 1 = 100

Problem 2 = 10100

Problem 3 = 4.712974e+159

No approximation of steps didn't affect the worst case time order of these algorithm as approximation were only of constant factor and these algorithm differ on N terms.

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

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