Re: how can i large divide?

Richard Heathfield <rjh@xxxxxxxxxxxxxxx> writes:

Bartc said:

<snip>

And I'm guessing my code was O(log2 n) because it worked in binary. Would
this make it faster or slower than O(log n) or is there no difference?

Big-O notation is a representation of computational complexity, not
runtime. The two are related, but not identical.

Let's say we have an O(6*n) algorithm. You can easily turn this into an
O(n) algorithm by buying a computer that works six times quicker than the
old one. You can even go to your vendor and say "we currently have a Model
X, but now we need something 6 times quicker than a Model X". He gives you
a Model Y, you give him much money, and suddenly you have O(n). So the
only real difference between O(6*n) and O(n) is a bit of cash,
right?

My main point is below but, for the record, O(6*n) = O(n) using = in
its strict mathematical sense. I think it is slightly misleading to
suggest any difference between them (i.e. "the only real difference"
is none at all).

But if we have an O(n*n) algorithm, we hit a problem.

and we also hit a terminology problem. Most people use O(...) when
they really want to say Theta(...). Merge sort is "an O(n*n)
algorithm" in a very precise sense. The number of comparisons
performed by a merge sort is a function MS(n) which is in O(n*n) just
as the number of comparisons done by bubble sort, BS(n), is in O(n*n).
Of course, MS(n) is also in O(n*log(n)) which BS(n) is not.

We should all get in the habit of saying "a Theta(n*n) algorithm" (if
it is true). Saying that something is O(n*n) is just a way of saying
that it's metric (time, space, no of comparisons, whatever) is no
"worse" than any other O(n*n) function, but it may be whole lot
better and big-O can't tell us that.

<for anyone who still cares>
O(n*n) is a set of functions, nothing more nothing less. Every
function, f, in O(n*n) has the property that one can find a C > 0 and
an x0 such that for all x > x0, abs(f(x)) < C*x*x.

Saying that a function f is in Theta(n*n) means that, eventually, its
absolute value is bounded both above and below by a positive multiple
of n*n. I.e. that we can find C1 and C2 > 0 and an x0 such that for
all x > x0, C1*x*x < abs(f(x)) < C2*x*x.

--
Ben.
.

Relevant Pages

  • Re: how can i large divide?
    ... Big-O notation is a representation of computational complexity, ... Let's say we have an Oalgorithm. ... You can also do so without buying a faster computer. ...
    (comp.lang.c)
  • Re: Comparing lists
    ... >> of computational complexity in terms of Big-Oh ... > algorithm will be, or how one algorithm compares to another. ... > complex set up for the merge-sort variant used for larger lists. ... > As for sets, they are based on dicts, which are effectively hash tables. ...
    (comp.lang.python)
  • Re: arithmetic in ZF
    ... Torkel manifestly obviously IS NOT *saying* that, ... > Or an algorithm can be given in terms ... > for computing a function from ... > naturals to naturals can be simulated ...
    (sci.logic)
  • Re: Koch on Quantum Consciousness
    ... "Noone, yet again, is saying that they can. ... biological systems do not necessarily reduce to anything as simple as ... recognise faces. ... In what sense then are they "reduced to" an algorithm? ...
    (uk.philosophy.humanism)
  • Re: Koch on Quantum Consciousness
    ... "Noone, yet again, is saying that they can. ... biological systems do not necessarily reduce to anything as simple as ... recognise faces. ... In what sense then are they "reduced to" an algorithm? ...
    (uk.philosophy.humanism)