Hacker News new | comments | show | ask | jobs | submit login

> anonymouz's interpretation is bizarre and definitely not how I'd think about the function.

It is usually understood that one measures the time complexity of an algorithm in the size of the input (only if the input is an integer, would it even make sense to measure it in the value of the input). So you may of course use whatever definition you like, but be careful that statements about the time complexity of certain things are often made without referring to the exact definitions used, and you may then misunderstand them.

For example, when people say "We don't know a polynomial-time algorithm to factor integers" they mean polynomial time in the size of the input (i.e., number of digits/bits of the integer). The problem would trivially be polynomial time if you allowed it to be polynomial in the integer itself.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact