linear hashing deletion ...write an analysis/demonstration of the Big O time for

Question

linear hashing deletion ...write an analysis/demonstration of the Big O time for the algorithm — show all work . give cost of each line in big oh notation please please please!

public void delete (Key key) if contains Ckey)) return inti hash key) while C! key. equals Ckeys [i])) (i 1) m keys [i] null vals Cil null i Ci 1) M; while (keys Lil null) Key keyToRedo keys Cil; Value valToRedo vals Cil; keys Lil null vals null; sli] put keyToRedo, val ToRedo) i Ci 1) 96 m; if (n 0 && n m/8) resize (m/2); Deletion for linear probing

Explanation / Answer

since there are M slots, the searching for the element to be deleted will be done max M times

1. if(!contains(key)) return = O(m) because key will be searched from iindex 0 to M-1 i.e. total M

2. int i=Hash.(key) = max M assignments = O(M)

3. while(!key.equals(keys[i])) i=(i+1)%m; when key will match, it will perform operation. hence: O(M)

total : O(M)+O(M)+O(M)+O(M)+O(M/8)= 4O(M)+O(M/8)

neglecting higher terms: complexity: O(M)

4. next while loop; while(keys[i]!= null) , all assignments max M times. hence, O(M)

5. if loop: n t0 M/8; hence O(M/8)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.