S2#3 | Algorithm Analysis | Discrete Math | Big 0 Notation The mode of an array
ID: 3830293 • Letter: S
Question
S2#3 | Algorithm Analysis | Discrete Math | Big 0 Notation
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 leftarrow A(1), f = 1 for i = 2 to n do if A(i) = A(i - f) then m leftarrow A(i), f leftarrow f+1 endif endfor What is the complexity of the above algorithm? Write a pseudocode for the recursive version of the above algorithm model (A, i, m, f) which computes the mode m and its frequency fin an ordered array A(1: i) where 1 lessthanorequalto i lessthanorequalto n. Obtain the complexity of the algorithm.Explanation / Answer
a) In the algorithm since the input is an ordered array list the time taken by the algorithm to compute mode and frequency is linear , hence the runtime is O(n) .
b ) The recursive algorithm to find the mode and frequency of an ordered array is
Algorithm (a,n,m,f)
Output : Mode m and frequency f of an ordered array A(1:n)
The time taken by third and fourth line of algortihm is O(1) and the total time taken is f(n) , therefore we get,
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.