5 ms·

The article doesn't make sense. It implies that the lower bound proved is exponential but much better than the conjectured lower bound (also exponential): "Kn

The article doesn't make sense. It implies that the lower bound proved is exponential but much better than the conjectured lower bound (also exponential): "Knuth had previously proved an exponential upper bound on the number of Topswops steps, and conjectured that one might also prove a matching lower bound. What Dr. Hal Sudborough and Dr. Linda Morales did, however, was to prove a lower bound that is much better than that proposed in Knuth’s conjecture..." However, the paper cited says “A Quadratic Lower Bound for Topswops”, so the lower bound proved is much worse than the one conjectured by Knuth.

RodgerTheGreat 16y ago
You have that backwards. An exponential bound (c^n) will massively dominate a quadratic bound (n^2). For lower bounds, smaller is better.
- amichail 16y ago
  No. For lower bounds, higher is better.
  - sonoffett 16y ago
    Yes, higher is better because it gives you a tighter bound when searching for Big-Theta: ie. if your algorithm is in O(2^n) and the previous lower bound was Omega(n^2), and someone proves a lower bound of Omega(2^n) then you know the problem is in Theta(2^n) and you can stop looking for a faster algorithm. It's worse in the sense that the problem takes more time to solve than if someone had found an algorithm in O(n^2). EDIT: spelling
rix0r 16y ago
Well, a quadratic lower bound is better than an exponential lower bound, in the sense that the problem could still turn out to not be in EXPTIME but in PTIME. It is worse in the sense that it tells us less about the actual complexity class the problem is in, so I guess it depends on what you interpret "better" to mean in this context.
- amichail 16y ago
  You could always say the lower bound is zero or some very small function. That's pointless and is not better in any sense.
  - cma 16y ago
    There are two notions of lower bound: lower bound like you are talking about (the function always takes longer than this to run for an input of size n) lower bound across all inputs of size n (the function never runs faster than this, given any possible input of size n) The two are different
    - sonoffett 16y ago
      I'm pretty sure your second definition is an upper bound (big-O) and the first definition is a lower bound (big-Omega). EDIT: adding a link to the wikipedia article defining Big-O and Big-Omega: http://en.wikipedia.org/wiki/Big_O_notation http://en.wikipedia.org/wiki/Big_O_notation
      - cma 16y ago
        Yeah I screwed that up, what I meant to refer to is this: >It is not contradictory however, to say that the worst-case >running time of insertion sort is [Big Omega](n^2), >since there exists an input that causes the algorithm >to take [Big Omega](n^2) time. >Introduction to Algorithms, 2nd Edition, p 46
dasht 16y ago
You are right. The article is a muddle. I think they meant: the quadratic lower bound is the highest yet proved -- not that it is "better" than Knuth's unproved conjecture.
- amichail 16y ago
  It's more likely that the person who wrote this article doesn't even know what a lower bound is.

RodgerTheGreat 16y ago

You have that backwards. An exponential bound (c^n) will massively dominate a quadratic bound (n^2). For lower bounds, smaller is better.

amichail 16y ago
No. For lower bounds, higher is better.
- sonoffett 16y ago
  Yes, higher is better because it gives you a tighter bound when searching for Big-Theta: ie. if your algorithm is in O(2^n) and the previous lower bound was Omega(n^2), and someone proves a lower bound of Omega(2^n) then you know the problem is in Theta(2^n) and you can stop looking for a faster algorithm. It's worse in the sense that the problem takes more time to solve than if someone had found an algorithm in O(n^2). EDIT: spelling

rix0r 16y ago

Well, a quadratic lower bound is better than an exponential lower bound, in the sense that the problem could still turn out to not be in EXPTIME but in PTIME. It is worse in the sense that it tells us less about the actual complexity class the problem is in, so I guess it depends on what you interpret "better" to mean in this context.

amichail 16y ago
You could always say the lower bound is zero or some very small function. That's pointless and is not better in any sense.
- cma 16y ago
  There are two notions of lower bound: lower bound like you are talking about (the function always takes longer than this to run for an input of size n) lower bound across all inputs of size n (the function never runs faster than this, given any possible input of size n) The two are different
  - sonoffett 16y ago
    I'm pretty sure your second definition is an upper bound (big-O) and the first definition is a lower bound (big-Omega). EDIT: adding a link to the wikipedia article defining Big-O and Big-Omega: http://en.wikipedia.org/wiki/Big_O_notation http://en.wikipedia.org/wiki/Big_O_notation
    - cma 16y ago
      Yeah I screwed that up, what I meant to refer to is this: >It is not contradictory however, to say that the worst-case >running time of insertion sort is [Big Omega](n^2), >since there exists an input that causes the algorithm >to take [Big Omega](n^2) time. >Introduction to Algorithms, 2nd Edition, p 46

dasht 16y ago

You are right. The article is a muddle. I think they meant: the quadratic lower bound is the highest yet proved -- not that it is "better" than Knuth's unproved conjecture.

amichail 16y ago
It's more likely that the person who wrote this article doesn't even know what a lower bound is.