Message #1807

From: schuma <mananself@gmail.com>
Subject: Re: God’s Number for n^3 cubes.
Date: Thu, 30 Jun 2011 08:42:30 -0000

Shevek,

You seem to have a very different understanding of the paper. In my understanding, they are showing that the god’s number itself = Theta(n^2*log(n)). But in your understanding, the number of operation to compute the god’s number is Theta(n^2*log(n)). I checked the paper again and hold my point.

In computational complexity, big-O notation is used to measure the computational time. But in other fields, it can be used to measure anything, in this paper, the god’s number itself. I wonder if you buy it or now.

Nan

— In 4D_Cubing@yahoogroups.com, "shevek1248" <shevek1248@…> wrote:
>
> I don’t usually post, but I wanted to make a quick correction:
>
> Big-O notation has nothing to do with the size of God’s Number for a n^3 cube, but with the number of computational operations needed to compute that number. For instance, an O(n^2) sort algorithm requires a number of operations proportional to the square of how many entries are being sorted.
>
> So anyway, the big-O is used for measuring time, not the scale of your answer. And, as a useful speed comparison, the difference of a factor of log(n) is approximately the difference between the best available sorting algorithm (O(n*log(n))) and your average high-schooler’s algorithm (O(n^2)). (Yes, yes, I know, log^2(n) =/= n, but it seemed like a good scale reference)
>
>