From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: `completion-in-region' Date: Sun, 11 Apr 2010 22:10:50 -0400 Message-ID: References: <493575A8A83B43BCB1AF49E239599A77@us.oracle.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: dough.gmane.org 1271038271 9600 80.91.229.12 (12 Apr 2010 02:11:11 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Mon, 12 Apr 2010 02:11:11 +0000 (UTC) Cc: Leo , Drew Adams , emacs-devel@gnu.org To: Lennart Borgman Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon Apr 12 04:11:09 2010 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1O197C-0004NQ-Lv for ged-emacs-devel@m.gmane.org; Mon, 12 Apr 2010 04:11:06 +0200 Original-Received: from localhost ([127.0.0.1]:44153 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O197B-0002EQ-Up for ged-emacs-devel@m.gmane.org; Sun, 11 Apr 2010 22:11:05 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1O1976-0002Da-Cx for emacs-devel@gnu.org; Sun, 11 Apr 2010 22:11:00 -0400 Original-Received: from [140.186.70.92] (port=48580 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O1973-0002D8-Hs for emacs-devel@gnu.org; Sun, 11 Apr 2010 22:11:00 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1O1970-0008Qd-B5 for emacs-devel@gnu.org; Sun, 11 Apr 2010 22:10:57 -0400 Original-Received: from ironport2-out.teksavvy.com ([206.248.154.181]:39034 helo=ironport2-out.pppoe.ca) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1O196x-0008Px-Je for emacs-devel@gnu.org; Sun, 11 Apr 2010 22:10:52 -0400 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AvsEAE8ewktMCqWu/2dsb2JhbACbQXK2J4UMBItG X-IronPort-AV: E=Sophos;i="4.52,186,1270440000"; d="scan'208";a="60642365" Original-Received: from 76-10-165-174.dsl.teksavvy.com (HELO pastel.home) ([76.10.165.174]) by ironport2-out.pppoe.ca with ESMTP; 11 Apr 2010 22:10:50 -0400 Original-Received: by pastel.home (Postfix, from userid 20848) id 6FC4F7F1B; Sun, 11 Apr 2010 22:10:50 -0400 (EDT) In-Reply-To: (Lennart Borgman's message of "Sun, 11 Apr 2010 23:06:44 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.50 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:123509 Archived-At: >> If you use ".*?a.*?b.*?c", then yes it gives the >> same matches but it also has the same O(N^3) worst case. > This is not the right place perhaps to educate me on this, but to me > it looks like just three linear searches with the summed length for > the searches equal to that of the candidate strings. Is not that O(N)? When matched against "ababab", it will do the following: - search for a in the string. - for each match of a, search for b in the remaining string. - for each match of b, search for c in the remaining string. These are 3 nested loops, each of them doing a number of iterations proportional to N, so you get O(N^3) complexity. Stefan