4 ms·

you get a linear time O(n) isEven function In complexity theory, the size of a problem is the number of bits to represent the input, so if the input integer is

you get a linear time O(n) isEven function In complexity theory, the size of a problem is the number of bits to represent the input, so if the input integer is i, then the size is n = log_2(i) so the algorithm is actually exponential in the number of bits it takes to represent the input.

trias 5y ago
is complexity theory constrained to binary representations? Why should it?
- Ar-Curunir 5y ago
  Every base except unary is a constant-factor away from binary, and so is irrelevant asymptotically. We don't use unary because it's artificially slow.
  - creata 5y ago
    See also: https://medium.com/@veedrac/why-unary-is-the-best-number-system-cc1e0edfb928 https://medium.com/@veedrac/why-unary-is-the-best-number-sys...
    - Ar-Curunir 5y ago
      That post is a joke, right?
      - deleted 5y ago
        [deleted]
dragontamer 5y ago
In a strict sense, you're right. But in practice, you're not. Case in point: matrix multiplication is commonly quoted as O(n^3) (naive), when in fact, the amount of data used is O(n^2), and therefore should be quoted as O(size^2) (quadratic) with respect to data-size. (EDIT: was bad at math for a second). But no, people mean "n-by-n matrix" has "O(n^3) naive" implementation. In practice, the "n" is just whatever is most convenient for a problem. In many cases, n is proportional to the input size. But in other cases (such as the famous matrix multiplication examples), n is the sqrt(input-size).
- jcranmer 5y ago
  > therefore should be quoted as O(size^2) (quadratic) It's actually O(size^1.5), not O(size^2). Well, assuming you're talking about θ(n) when you mean O(n) as most people do. [If you're not familiar with the difference, Θ(f(n)) means a function that grows as fast as f(n), up to a constant, whereas O(f(n)) is a function that grows no faster. So n^2 is O(n^3) but not Θ(n^3).]
- wittycardio 5y ago
  But it's actually quite relevant here. For example with the informal notation you can find all the prime factors of a number N in "O(N)" time , if someone doesn't understand the distinction then they might believe that theres a polytime algorithm for factorization.

trias 5y ago

is complexity theory constrained to binary representations? Why should it?

Ar-Curunir 5y ago
Every base except unary is a constant-factor away from binary, and so is irrelevant asymptotically. We don't use unary because it's artificially slow.
- creata 5y ago
  See also: https://medium.com/@veedrac/why-unary-is-the-best-number-system-cc1e0edfb928 https://medium.com/@veedrac/why-unary-is-the-best-number-sys...
  - Ar-Curunir 5y ago
    That post is a joke, right?
    - deleted 5y ago
      [deleted]

dragontamer 5y ago

In a strict sense, you're right. But in practice, you're not. Case in point: matrix multiplication is commonly quoted as O(n^3) (naive), when in fact, the amount of data used is O(n^2), and therefore should be quoted as O(size^2) (quadratic) with respect to data-size. (EDIT: was bad at math for a second). But no, people mean "n-by-n matrix" has "O(n^3) naive" implementation. In practice, the "n" is just whatever is most convenient for a problem. In many cases, n is proportional to the input size. But in other cases (such as the famous matrix multiplication examples), n is the sqrt(input-size).

jcranmer 5y ago
> therefore should be quoted as O(size^2) (quadratic) It's actually O(size^1.5), not O(size^2). Well, assuming you're talking about θ(n) when you mean O(n) as most people do. [If you're not familiar with the difference, Θ(f(n)) means a function that grows as fast as f(n), up to a constant, whereas O(f(n)) is a function that grows no faster. So n^2 is O(n^3) but not Θ(n^3).]
wittycardio 5y ago
But it's actually quite relevant here. For example with the informal notation you can find all the prime factors of a number N in "O(N)" time , if someone doesn't understand the distinction then they might believe that theres a polytime algorithm for factorization.