what is the worse case running time of the algorithm below, Use the big theta no
ID: 3671378 • Letter: W
Question
what is the worse case running time of the algorithm below, Use the big theta notation and justify your answer.
for (i =0; i <= n-1; i++){
store xi in position Hash_f(xi) in table Tx
} // create a hash table Tx with n buckets
for (j=0; j<=n-1; j++){
store z-yj in position Hash_f(z-yj) in table Tm
} // create a hash table Tm with n buckets
for (q=0; q<=n-1; q++){
for each item x in bucket k of Tx {
for each item m in bucket k of Tm {
if x=m {
return true;}
}
}
}
return false;
Explanation / Answer
first for loo: O(n)
second for loop: O(n)
From first two loop, HahTable Tx and HashTable Tm has created, each with n items
so, at last we have 3 nested for loop, each is running for n times
so time complexity: O(n^3)
Overall, T(n) = O(n)+O(n)+O(n^3) = O(n^3)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.