If you consider hash table insertion as O(1) then it is O(n) I guess.