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 

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

1 Expert Approved Answer
Step: 1 Unlock

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

blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!