This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch] sort and group case labels
- From: Steven Bosscher <stevenb at suse dot de>
- To: Joern Rennecke <joern dot rennecke at superh dot com>
- Cc: Steven Bosscher <stevenb at suse dot de>,Joern Rennecke <joern dot rennecke at superh dot com>,Steven Bosscher <stevenb at suse dot de>, gcc-patches at gcc dot gnu dot org
- Date: Wed, 26 May 2004 13:51:06 +0200 (CEST)
- Subject: Re: [patch] sort and group case labels
- Organization: SuSE Linux AG
- References: <200405261147.i4QBlmt09718@linsvr1.uk.superh.com>
On May 26, 2004 01:47 PM, Joern Rennecke <joern.rennecke@superh.com> wrote:
> > It is _worst_case_ O(N^2) but in practice it is O(N log N).
> > (And quicksort is typically faster than algorithms with a worst-case
> > O(N log N) time complexity).
>
> + for (i = 0; i < old_size - 2; i++)
> + {
> + tree base_case, base_high, base_label, type;
> +
> + base_case = TREE_VEC_ELT (old_labels, i);
> + if (! base_case)
> + abort ();
> +
> + type = TREE_TYPE (CASE_LOW (base_case));
> + base_label = CASE_LABEL (base_case);
> + base_high = CASE_HIGH (base_case) ?
> + CASE_HIGH (base_case) : CASE_LOW (base_case);
> +
> + for (j = i; j < old_size - 2; j++)
>
> That looks solidly O(n^2) to me.
Look again then. It is not.
[ hint: a few lines down, i = j ]
Gr.
Steven