Question: Consider the following algorithm. Count (A[], n) /* A=array of n integers */ Hash Table.Init(); S.Init(); /* S is a stack */ for io
Consider the following algorithm. Count (A[], n) /* A=array of n integers */ Hash Table.Init(); S.Init(); /* S is a stack */ for io 1 to n do for i 1 to n do K A[io] * A[i]; if (Hash Table. Member(K)) then | Hash Table.Add(K,1) else Hash Table. Insert (K,1) S.Push(K) end end end while (S.IsNotEmpty()) do K - S.Pop(); count Hash Table. Retrieve(K); Report "Number of occurrence of K= count"; end Assume that the hash table used in this algorithm is implemented using CHAINED HASHING and has size n. (Note that far more than n elements are inserted in the hash table.) What is the worst case running time of algorithm Count? Justify your solution and show your work. What is the expected running time of algorithm Count? Justify your solution and show your work.
Step by Step Solution
3.37 Rating (150 Votes )
There are 3 Steps involved in it
To analyze the worstcase and expected running time of the Count algorithm we need to consider the operations performed in each step of the algorithm W... View full answer
Get step-by-step solutions from verified subject matter experts
