CareerCup

Well to get to the point where the entry is, the complexity will be O(1)
But if a chaining mechanism is used, we would have to look at each element in the chain (if the chain is a linked list) and the complexity under worst case condition would be O(n)

Vague, really, not incomplete. Part of the question is understanding that it does depend on hashing algorithm.

It really depends on the actual implementation.
Chintan, if you believe that it takes O(ln n) to find a duplicate in the linked list, then the linked list(which is used for handling collisions) must be sorted at anytime. If you want to have such a hashtable, the insertion will be O(ln n) as well since it has to be placed at the right position to ensure that the linked list is sorted.

The information in the question is incomplete. The worst case time depends on the hash function and the strategy to resolve the conficts. Suppose the hash function is f(i) = 1 and if chaining is used you will always need n comparisons. This time also depends on the size of the hash table and number of nodes already inserted in the hash table, that is load factor of the hash table is also one parameter which would determine this. But in theroetical sense the worst possible time for hashtable insertion is O(n)

again an ambiguous question.

It really depends what collision technique is being used when doin insertion in hash table.

If we are sure that there will not be any collision then it is o(1).

If it is open addressing, it really depends on hash function we use for rehashing. Could be as much as O(n) or it can be the case that we do not find any empty space because of the nature of the rehasing function and already populated values in hash table.

If chaining is used, worst case can be O(n).

Assuming that the hash table is implemented as an array, there are collisions, and chaining is used to handle them.

Insert can still be done in O(1)? If a collision occurs, instead of traversing the entire list and inserting the new value at the end, Insert it at the start.

does this make sense ?

It is O(1 + alpha)

where alpha = n/m

m = number of slots in the hash table
n = total number of elements that u are trying to put in the hash table.

--check Introduction to algorithms by cormen

O(n) in worst case when all the keys get mapped to the same slot.

But, hashtable can't have duplicate value, so in order to find out
whether it is duplicate or not, it first takes o(lon n) time, and
then just 0(1) to insert it. Isn't it?