Talk:Fast algorithms

This is the talk page of a redirect that targets the page:
• Time complexity
Because this page is not frequently watched, present and future discussions, edit requests and requested moves should take place at:
• Talk:Time complexity

So what?[edit]

This article is defining a notion of a fast algorithm for evaluating a function on large numbers (i.e. numbers for which we need to care about bit complexity instead of the more usual RAM model) by relating the complexity of the function evaluation algorithm to the complexity of ~~matrix~~ multiplication by a $log^{c}(n)$ factor.

But why is this definition important? There's no deep result claimed here like saying for instance that you cannot do better than that for an arbitrary function. Is this a conjecture article? Pcap ping 23:42, 20 August 2009 (UTC)[reply]

Wrong info on matrix multiplication?[edit]

It appears to contradict Coppersmith–Winograd algorithm, i.e. the complexity cannot be below O(n²), unless I'm missing something... Pcap ping 23:58, 20 August 2009 (UTC)[reply]

It's not matrix multiplication. It's just multiplication. The stated time-complexity is of the Schönhage–Strassen algorithm. We do know a faster one now: Fürer's algorithm --Robin (talk) 00:04, 21 August 2009 (UTC)[reply]

Oops. Anyway, complexity of M(n) is not essential info in here, so I've replaced it with a link. Pcap ping 00:14, 21 August 2009 (UTC)[reply]

Scope in lead vs body[edit]

The lead claims that "Fast algorithms" is a field of study, but in the body all we find out is that "Fast algorithms" are class of algorithms, essentially those numeric algorithms that have Õ(n) bit complexity. That's not quite backing up the claim that this is a field of study. Pcap ping 08:26, 21 August 2009 (UTC)[reply]

Notability[edit]

So has anyone been able to establish notability for this concept? If not, I'm going to nominate this for deletion. If this concept of a "fast algorithm" is slightly notable, it can be mentioned in one line at analysis of algorithms or some such article. We don't need a full article for this one-line concept. --Robin (talk) 14:52, 22 August 2009 (UTC)[reply]

You could just redirect it there. It avoids having to deal with the potentially uninformed opinions of those that might be impressed by the long reference list. If the concept is somehow known under another name in the English literature (that neither of us knows about), a non-admin ca (i) notice it, and (ii) resurrect the article much more easily with full history. Pcap ping 15:08, 22 August 2009 (UTC)[reply]

Sounds good. Will do just that. --Robin (talk) 17:44, 22 August 2009 (UTC)[reply]