The cost of computing a trivial hash function is effectively zero, so the time complexity is $\mathcal{O}(1)$; however, if I assign $n$ variables using the hash function, is the complexity $\mathcal{O}(n)$.

For example, the pseudo code would look like this:

for i=1 to n
   var[i] = hash[data[i]];

The only operation that is being performed is the assignment operation, but in complexity theory, it seems that the assignment operation is not usually included in defining the complexity.


Your question is ill-defined, and it's precisely that that I believe to be your misunderstanding.

There isn't an inherent cost in Landau notation, or any complexity analysis measure for that matter. You first need to define a model, by defining exactly what consists of an operation.

For example you could model only assignments, in which case the complexity is $n$. You could also model only hash function calls, in which case the complexity is also $n$. Or you could consider both to be one unit of time, in which case the complexity is $2n$.

Or perhaps your hash function is $100$ times slower than an assignment, which we assign cost $1$. Then your complexity would be $101n$.

  • $\begingroup$ I understand. This actually answers my question perfectly. Thanks! $\endgroup$ – Ralff Feb 7 '18 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.