This is a misunderstanding, you must have answered to my reply after ithayer edited his comment, the initial comment said "constant time".