From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gsl-discuss-return-5427-listarch-gsl-discuss=sources.redhat.com@sourceware.org>
Received: (qmail 27851 invoked by alias); 12 May 2009 08:44:43 -0000
Received: (qmail 27842 invoked by uid 22791); 12 May 2009 08:44:42 -0000
X-SWARE-Spam-Status: No, hits=-0.4 required=5.0
	tests=AWL,BAYES_50,SPF_PASS
X-Spam-Check-By: sourceware.org
Received: from mail.network-theory.co.uk (HELO mail.network-theory.co.uk) (66.199.228.187)
    by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 12 May 2009 08:44:37 +0000
Date: Tue, 12 May 2009 08:44:00 -0000
Message-ID: <m33aba3e4m.wl%bjg@network-theory.co.uk>
From: Brian Gough <bjg@network-theory.co.uk>
To: Gideon Simpson <simpson@math.toronto.edu>
Cc: gsl-discuss@sourceware.org
Subject: Re: DHT performance
In-Reply-To: <21FF16B9-8781-4C1E-BC11-0C90C4123DE0@math.toronto.edu>
References: <21FF16B9-8781-4C1E-BC11-0C90C4123DE0@math.toronto.edu>
User-Agent: Wanderlust/2.14.0 (Africa) Emacs/22.2 Mule/5.0 (SAKAKI)
MIME-Version: 1.0 (generated by SEMI 1.14.6 - "Maruoka")
Content-Type: text/plain; charset=US-ASCII
X-Message-Mac: 8b5751832a477981fbb82b712d3bbe11
Mailing-List: contact gsl-discuss-help@sourceware.org; run by ezmlm
Precedence: bulk
List-Id: <gsl-discuss.sourceware.org>
List-Subscribe: <mailto:gsl-discuss-subscribe@sourceware.org>
List-Archive: <http://sourceware.org/ml/gsl-discuss/>
List-Post: <mailto:gsl-discuss@sourceware.org>
List-Help: <mailto:gsl-discuss-help@sourceware.org>, <http://sourceware.org/ml/#faqs>
Sender: gsl-discuss-owner@sourceware.org
X-SW-Source: 2009-q2/txt/msg00008.txt.bz2

At Sat, 9 May 2009 20:34:08 -0400,
Gideon Simpson wrote:
> 
> Am I right that the DHT algorithm is not *fast* in the sense that it's  
> O(N^2)?

I believe that's true, yes.  As I understand it, the advantage is that
the overall constant in the runtime is small due to everything being
precomputed.