The mode of an array A(1: n) is the most frequently repeated element. The follow
ID: 3795546 • Letter: T
Question
The mode of an array A(1: n) is the most frequently repeated element. The following very elegant iterative algorithm computes the mode and its frequency in an ordered array A.
algorithm mode (A, n, m, f)
// mode m and its frequency f in an ordered array A(1: n)
m A(1), f = 1
for i = 2 to n do
if A(i) = a(i – f) then
m A(i), f f + 1
endif
endfor
What is the complexity of the above algorithm?
(a) Write a pseudocode for the recursive version of the above algorithm mode1 (A, i, m, f) which computes the mode m and its frequency f in an ordered array A(1: i) where 1 i n. Obtain the complexity of the algorithm.
Explanation / Answer
The complexity of the above algorithm is O(n)
//recursive algorithm
algorithm mode1 (A, i, m, f)
// mode m and its frequency f in an ordered array A(1: n)
if i >= (i-f)
return A(i)
end if
if A(i) = a(i – f) then
m = A(i)
f = f+1
end if
m mode1(A, i+1, m, f)
//time complexity is O(n)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.