[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: queue-length should be O(1) ?

This page is part of the web mail archives of SRFI 117 from before July 7th, 2015. The new archives for SRFI 117 contain all messages, not just those from before July 7th, 2015.

To: Takashi Kato <ktakashi@xxxxxxxxx>
Subject: Re: queue-length should be O(1) ?
From: Kevin Wortman <kwortman@xxxxxxxxx>
Date: Fri, 5 Dec 2014 12:17:28 -0800
Cc: srfi-117@xxxxxxxxxxxxxxxxx
Delivered-to: srfi-117@xxxxxxxxxxxxxxxxx
Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=k5G7Gp1lVDsPYPG9Uxbucmnr0Y6z4wYwgW34GGU7WW0=; b=HfAf0X1W80Yuykl067LxxwUpheleltWWXtPpDOMvOEEl5NWXRFlPdtA6eD8Yn8BSth 9dmg41TfHAxKJTg1gs80GJYNEhIh745UC4ZkHbrSvs7dc56cj4hX4KR85mFHpy8ceslw erBraUW1EOGno5jqHiZYKtDimtcKidyL1s8S5EBjwgjQZH7QUD1adiZxaMW470BNk/1C SDjXyvfcbOkKkrKUtW2WIX5lrP1UbLb1SaZXhhxu3nSS6GXiRdIDTrxkO4q/SgquphgO OzT34HoiVVzYIQhm3OZhOYziru8H4/suEUDP5h+XHJ4CgwFE6x6TMHhq0H6rAgsBpQGJ 6llQ==
In-reply-to: <547F52C9.4030708@ymail.com>
References: <20141203.092501.756592971992382910.hartrumpf@gmx.net> <20141203131906.GA29310@mercury.ccil.org> <547F52C9.4030708@ymail.com>

Isn't it, then, better not to specify the order so that implementation
may choose how it's implemented at least for this particular procedure?
Or do the orders indicate worst cases?

I have the same question/comment. Technically, by the definition of O ( http://www.phil.uu.nl/datastructuren/10-11/knuth_big_omicron.pdf ), O(1) is a subset of O(n), so if a procedure takes O(1) time it is sound to also say that it takes O(n) time. So an implementation with an O(1) queue-length would comply with the SRFI, but I get the sense that's not what's intended. ϴ (theta) notation can be used to indicate that a procedure be linear and no faster, i.e. ϴ(n).

Regards,

Kevin Wortman

References:
- queue-length should be O(1) ?
  - From: Sven Hartrumpf
- Re: queue-length should be O(1) ?
  - From: John Cowan
- Re: queue-length should be O(1) ?
  - From: Takashi Kato

Prev by Date: Re: make-queue-with-list and make-queue-with-first-last
Next by Date: Re: make-queue-with-list and make-queue-with-first-last
Previous by thread: Re: queue-length should be O(1) ?
Next by thread: Sample implementation missing queues-test.scm?
Index(es):
- Date
- Thread