Consider the following algorithm. Count (A[], n) /* A=array of n integers */ Hash Table.Init(); S.Init();...

  

Transcribed Image Text:

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. 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.

Answer rating: 100% (QA)

The image shows an algorithm named Count that takes an array A of n integers It initializes a hash table and a stack and then proceeds to perform calc... View the full answer