From: Kaartic Sivaraam <kaarticsivaraam91196@gmail.com>
To: Stefan Beller <sbeller@google.com>, Jeff King <peff@peff.net>
Cc: "git@vger.kernel.org" <git@vger.kernel.org>
Subject: Re: [PATCH 10/10] add UNLEAK annotation for reducing leak false positives
Date: Tue, 12 Sep 2017 20:04:52 +0530 [thread overview]
Message-ID: <1505226892.27800.37.camel@gmail.com> (raw)
In-Reply-To: <CAGZ79kYmZJ8k2=SVrx9vpEXoKhRBGwu8J=fS=cYiCLdKf+nDGA@mail.gmail.com>
> On Tue, 2017-09-05 at 15:05 -0700, Stefan Beller wrote:
>
> After having a sneak peak at the implementation
> it is O(1) in runtime for each added element, and the
> space complexity is O(well).
>
Incidentally I was reading about "complexity of algorithms" and there
was the following paragraph in the book,
Unfortunately, as Knuth observed, big-O notation is often used by careless writers and
speakers as if it had the same meaning as big-Theta notation. Keep this in mind when you see
big-O notation used. The recent trend has been to use big-Theta notation whenever both upper
and lower bounds on the size of a function are needed.
So, if my interpretation is correct the above usage of O(1) and O(well)
should have been Θ(1) and Θ(well).
--
Kaartic
next prev parent reply other threads:[~2017-09-12 14:34 UTC|newest]
Thread overview: 42+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-09-05 13:01 [PATCH 0/10] towards clean leak-checker output Jeff King
2017-09-05 13:03 ` [PATCH 01/10] test-lib: --valgrind should not override --verbose-log Jeff King
2017-09-05 13:04 ` [PATCH 02/10] test-lib: set LSAN_OPTIONS to abort by default Jeff King
2017-09-05 13:04 ` [PATCH 03/10] add: free leaked pathspec after add_files_to_cache() Jeff King
2017-09-05 13:04 ` [PATCH 04/10] update-index: fix cache entry leak in add_one_file() Jeff King
2017-09-05 13:04 ` [PATCH 05/10] config: plug user_config leak Jeff King
2017-09-05 13:04 ` [PATCH 06/10] reset: make tree counting less confusing Jeff King
2017-09-05 13:04 ` [PATCH 07/10] reset: free allocated tree buffers Jeff King
2017-09-05 13:04 ` [PATCH 08/10] repository: free fields before overwriting them Jeff King
2017-09-05 13:05 ` [PATCH 09/10] set_git_dir: handle feeding gitdir to itself Jeff King
2017-09-07 19:06 ` Brandon Williams
2017-09-05 13:05 ` [PATCH 10/10] add UNLEAK annotation for reducing leak false positives Jeff King
2017-09-05 22:05 ` Stefan Beller
2017-09-07 9:17 ` Jeff King
2017-09-07 20:38 ` Stefan Beller
2017-09-12 14:34 ` Kaartic Sivaraam [this message]
2017-09-12 15:05 ` Jeff King
2017-09-13 7:13 ` Kaartic Sivaraam
2017-09-06 17:16 ` Martin Ågren
2017-09-07 9:00 ` Jeff King
2017-09-12 13:41 ` Kaartic Sivaraam
2017-09-12 15:29 ` Jeff King
2017-09-13 6:44 ` Kaartic Sivaraam
2017-09-05 17:50 ` [PATCH 0/10] towards clean leak-checker output Martin Ågren
2017-09-05 19:02 ` Jeff King
2017-09-05 20:41 ` Martin Ågren
2017-09-06 12:39 ` Jeff King
2017-09-06 1:42 ` Junio C Hamano
2017-09-06 12:28 ` [PATCH 0/2] simplifying !RUNTIME_PREFIX Jeff King
2017-09-06 12:30 ` [PATCH 1/2] system_path: move RUNTIME_PREFIX to a sub-function Jeff King
2017-09-06 13:23 ` Johannes Schindelin
2017-09-06 13:27 ` Jeff King
2017-09-06 12:32 ` [PATCH 2/2] git_extract_argv0_path: do nothing without RUNTIME_PREFIX Jeff King
2017-09-08 6:38 ` [PATCH v2 10/10] add UNLEAK annotation for reducing leak false positives Jeff King
2017-09-19 20:45 ` Jonathan Tan
2017-09-19 21:03 ` Jeff King
2017-09-19 21:34 ` [PATCH for jk/leak-checkers] git-compat-util: make UNLEAK less error-prone Jonathan Tan
2017-09-19 21:46 ` Jeff King
2017-09-19 22:10 ` [PATCH for jk/leak-checkers v2] " Jonathan Tan
2017-09-20 1:45 ` [PATCH v2 10/10] add UNLEAK annotation for reducing leak false positives Junio C Hamano
2017-09-20 2:28 ` Jeff King
2017-09-20 5:12 ` Junio C Hamano
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1505226892.27800.37.camel@gmail.com \
--to=kaarticsivaraam91196@gmail.com \
--cc=git@vger.kernel.org \
--cc=peff@peff.net \
--cc=sbeller@google.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.