From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gentoo-dev+bounces-54446-garchives=archives.gentoo.org@lists.gentoo.org>
Received: from lists.gentoo.org (pigeon.gentoo.org [208.92.234.80])
	by finch.gentoo.org (Postfix) with ESMTP id 12288138010
	for <garchives@archives.gentoo.org>; Wed,  5 Sep 2012 10:45:54 +0000 (UTC)
Received: from pigeon.gentoo.org (localhost [127.0.0.1])
	by pigeon.gentoo.org (Postfix) with SMTP id 6443421C00B;
	Wed,  5 Sep 2012 10:45:24 +0000 (UTC)
Received: from mail-bk0-f53.google.com (mail-bk0-f53.google.com [209.85.214.53])
	by pigeon.gentoo.org (Postfix) with ESMTP id A7DF2E07BA
	for <gentoo-dev@lists.gentoo.org>; Wed,  5 Sep 2012 10:44:37 +0000 (UTC)
Received: by bkwj4 with SMTP id j4so169079bkw.40
        for <gentoo-dev@lists.gentoo.org>; Wed, 05 Sep 2012 03:44:36 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20120113;
        h=mime-version:sender:in-reply-to:references:date
         :x-google-sender-auth:message-id:subject:from:to:content-type;
        bh=OfMO3+sVHWEhLDPzJBXzJJByTyw8hZuZ/LE839euxFU=;
        b=oFK0johEtcJQcWQSIg5VeV8GOBNoJChFrZhJ4nC1H4Yp64/Uc79UoJpsU+yhJUaSrf
         LQ73bAiSWg6V03ADDdVpdg4E9afLFEdprPmG3xTv6uM6uK2uiXElvFCapYgIj+vYpVWJ
         ypRvLqz+qKthqWAT9IDuvARswrWAKtRLeTpc0qJ0l/cqL5q+pzTGyC2xzTJn1f/lFXU/
         ncRBDpCXoQCHBoYPSUts3K7SOOD6Orr29Y8HP0ntFM/95buYQRMwB1qwObV9VZCNCyuX
         4GJhn5DVJPtAZjDGtLm7o94aX4rMPpetpuuTZ3wWclgZp+VM6cd91kijGC5hNygPlr6q
         v4VQ==
Precedence: bulk
List-Post: <mailto:gentoo-dev@lists.gentoo.org>
List-Help: <mailto:gentoo-dev+help@lists.gentoo.org>
List-Unsubscribe: <mailto:gentoo-dev+unsubscribe@lists.gentoo.org>
List-Subscribe: <mailto:gentoo-dev+subscribe@lists.gentoo.org>
List-Id: Gentoo Linux mail <gentoo-dev.gentoo.org>
X-BeenThere: gentoo-dev@lists.gentoo.org
Reply-to: gentoo-dev@lists.gentoo.org
MIME-Version: 1.0
Received: by 10.204.154.211 with SMTP id p19mr9343628bkw.12.1346841876661;
 Wed, 05 Sep 2012 03:44:36 -0700 (PDT)
Sender: freemanrich@gmail.com
Received: by 10.205.65.136 with HTTP; Wed, 5 Sep 2012 03:44:36 -0700 (PDT)
In-Reply-To: <CAN3AtvoQ0mgt6r_Ud0vaPH8Wy-baPh-YgTaqF2LmK5ZwXEteuQ@mail.gmail.com>
References: <50411874.4060204@gentoo.org>
	<20120831214611.088b3f50@googlemail.com>
	<50469795.2070901@gentoo.org>
	<CAN3AtvoQ0mgt6r_Ud0vaPH8Wy-baPh-YgTaqF2LmK5ZwXEteuQ@mail.gmail.com>
Date: Wed, 5 Sep 2012 06:44:36 -0400
X-Google-Sender-Auth: n8LoxtECyJpXW-XPHbWYK_Mkscc
Message-ID: <CAGfcS_mPZpe9B88KjDTDdMDe4NLsMECvdLcCnp3HLa1Vx3uxqQ@mail.gmail.com>
Subject: Re: [gentoo-dev] HDEPEND (host dependencies for cross-compilation)
 for EAPI 5?
From: Rich Freeman <rich0@gentoo.org>
To: gentoo-dev@lists.gentoo.org
Content-Type: text/plain; charset=ISO-8859-1
X-Archives-Salt: 0746de43-e756-48f6-86ab-2848d8a0e623
X-Archives-Hash: e147b65bb4579bbc35985cdb449469e4

On Wed, Sep 5, 2012 at 3:19 AM, Fabio Erculiani <lxnay@gentoo.org> wrote:
> The complexity would become:
> O((b + r + p) * P)
> b = amount of buildtime dependencies
> r = amount of runtime dependencies
> p = amount of post-dependencies
> P = amount of packages i need to apply the filter to
>
> Instead of just:
> O(b * P)

Well, actually, in both cases the complexity is O(n), assuming you
only need to make a constant number of passes through the deps per
package.

The whole point of O notation is that it is about how it scales, not
how long it takes.  An O(n) algorithm can actually be slower than an
O(n^n) algorithm even on a large dataset.  However, the key is that at
some point if the dataset gets large enough the O(n) algorithm will
always become faster.

I tend to agree with Cirian though - the time for some code to run
through the dependencies array and do something isn't going to be very
high.  If a piece of code has to do it many times there is nothing
that says the package manager can't index it.

Rich