5 ms·

Get that n out of the exponent -- that is waay too slow. Maybe you meant O(n^3*log(2))? That exponent is definitely a constant.

btilly 6y ago
We have better than that. I think that what was meant is O(n^2*log(n))
- nightcracker 6y ago
  That isn't just what's meant, that's also what's written.
  - btilly 6y ago
    The way that it was written didn't disambiguate whether or not the log is part of the exponent. Putting the * in there disambiguated that.
    - nightcracker 6y ago
      It doesn't. The multiplication is implied and it would have the same precedence as explicitly putting * there. So either both are ambiguous or neither is (and it isn't, the poster was just mistaken).
      - btilly 6y ago
        I'm not sure why you think that it is implied. I know that I have a lot of math background, and my brain read that log(n) as part of the exponent. I figure that if I read it that way, you have to expect that others will as well.
        nightcracker 6y ago
        No matter how you read a^b log(c), the multiplication is implied. The original confusion is whether it's to be read as (a^b)log(c) or a^(b log(c)). a^b*log(c) simply removes the implied multiplication, but it does not change whether that should be read as (a^b)*log(c) or a^(b*log(c)) and thus does not resolve the original confusion.
jessriedel 6y ago
I don't know if he edited his comment, but as it is currently written the log is not in the exponent under standard order of operations. Also, putting a constant factor like log(2) inside big-O notation is meaningless.
- kadoban 6y ago
  Constant factors in exponents are _not_ meaningless. One of those cases where the rules-of-thumb bite you.
  - jessriedel 6y ago
    I didn't claim that. The log(2) term is multiplied, and that's implied by my use of "factor", which in this context is always understood to mean multiplicative factor.
    - kadoban 6y ago
      You're correct. I think this comes down to confusion on the operator precedence. I read it as O(n^(3 log 2)) because otherwise it's kind of very obviously not correct (no way it's n^3, that's already known), but should have stated that, because according to usual notation/precedence it's not that.

btilly 6y ago

We have better than that. I think that what was meant is O(n^2*log(n))

nightcracker 6y ago
That isn't just what's meant, that's also what's written.
- btilly 6y ago
  The way that it was written didn't disambiguate whether or not the log is part of the exponent. Putting the * in there disambiguated that.
  - nightcracker 6y ago
    It doesn't. The multiplication is implied and it would have the same precedence as explicitly putting * there. So either both are ambiguous or neither is (and it isn't, the poster was just mistaken).
    - btilly 6y ago
      I'm not sure why you think that it is implied. I know that I have a lot of math background, and my brain read that log(n) as part of the exponent. I figure that if I read it that way, you have to expect that others will as well.
      - nightcracker 6y ago
        No matter how you read a^b log(c), the multiplication is implied. The original confusion is whether it's to be read as (a^b)log(c) or a^(b log(c)). a^b*log(c) simply removes the implied multiplication, but it does not change whether that should be read as (a^b)*log(c) or a^(b*log(c)) and thus does not resolve the original confusion.

jessriedel 6y ago

I don't know if he edited his comment, but as it is currently written the log is not in the exponent under standard order of operations. Also, putting a constant factor like log(2) inside big-O notation is meaningless.

kadoban 6y ago
Constant factors in exponents are _not_ meaningless. One of those cases where the rules-of-thumb bite you.
- jessriedel 6y ago
  I didn't claim that. The log(2) term is multiplied, and that's implied by my use of "factor", which in this context is always understood to mean multiplicative factor.
  - kadoban 6y ago
    You're correct. I think this comes down to confusion on the operator precedence. I read it as O(n^(3 log 2)) because otherwise it's kind of very obviously not correct (no way it's n^3, that's already known), but should have stated that, because according to usual notation/precedence it's not that.