symbol table search

Question

Access time of the symbol table will be logarithmic, if it is implemented by a

• A. linear list            
• B. search tree              
• C. hash table          
• D. none of the above

Comments

ISRO 2016

---

Options a

Answer 1

A. Linear list : on average O(n/2) i.e linear complexity

B. Search tree : on aaverage O(logn) i.e. logarithmic complexity.        //Answer

C. Hash table : Perfect Hashing leads to  O(1) i.e. constant complexity.

Comments

how???

---

thank you sir.i was wrong . bst has average case of logn

---

if non of these is the option and we have such methods which will give time complexity always o(logn) why we will take average and one more thing O(1) constant time for perfect hashing . how ??

---

why have you consider avg case in case of search tree ..If tree is not balanced it can be skewed in that case complexity will be o(n). so there is no point of considering avg case in case of search tree just to match the answer . A fair decision should be either to consider all best case or worst case....the safest assumption is to go with option D. 

Answer 2

I feel it should be hash table as  hashing using linear probing has a success rate of O{(1/x) *log(1/(1-x)) }

where x is load factor i.e

x = number of entries filled up / total number of places/entries  that can be  filled in table

Comments

even linear probing has the retrival time of o(n). how it can be log n.

---

i again got confused.if we insert using linear probing and our location can be found in that time then w must be able to search even . i am very  confused

---

linear probing can i feel but provided keys are is well distributed  hash function.this is the assumption just coz lookup funtion i.e to search using probing technique has the time complexity of that i mentioned

---

ha.lekin probe toh waha se suru hoga  jo hash function compute karega na. maine ye assume kar ke bola ki randomly ya oneafter other hash function insert nehi karti hain.but it distributs uniformly. tas y i am confused.i got it but still i feel it depends on hash function.  i feel it depends on hash function