From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Thread: 103376,703c4f68db81387d
X-Google-Thread: 109fba,703c4f68db81387d
X-Google-Thread: 115aec,703c4f68db81387d
X-Google-Thread: f43e6,703c4f68db81387d
X-Google-Attributes: gid103376,gid109fba,gid115aec,gidf43e6,public
X-Google-Language: ENGLISH,ASCII-7-bit
Path: 
 g2news1.google.com!news4.google.com!news.glorb.com!npeer.de.kpn-eurorings.net!newsfeed.arcor.de!news.arcor.de!not-for-mail
Date: Wed, 23 Mar 2005 12:06:31 +0100
From: Georg Bauhaus <sb463ba@user1.uni-duisburg.de>
User-Agent: Debian Thunderbird 1.0 (X11/20050116)
X-Accept-Language: en-us, en
MIME-Version: 1.0
Newsgroups: comp.lang.ada,comp.lang.c++,comp.realtime,comp.software-eng
Subject: Re: Teaching new tricks to an old dog (C++ -->Ada)
References: <4229bad9$0$1019$afc38c87@news.optusnet.com.au>
 <1110032222.447846.167060@g14g2000cwa.googlegroups.com>
 <871xau9nlh.fsf@insalien.org>
 <3SjWd.103128$Vf.3969241@news000.worldonline.dk>
 <87r7iu85lf.fsf@insalien.org> <1110052142.832650@athnrd02>
 <d0dkq6$781$1@titan.btinternet.com>
 <1110284070.410136.205090@o13g2000cwo.googlegroups.com>
 <395uqaF5rhu2mU1@individual.net> <uk6oigfzi.fsf@obry.org>
 <1110329098.642196@athnrd02> <u3bv5gq0y.fsf@obry.org>
 <1110361741.551255@athnrd02>
 <422edaec$0$26554$9b4e6d93@newsread4.arcor-online.net>
 <d0n0vg$4oa$1@s1.news.oleane.net>
 <WKK%d.193$FN4.28@newssvr21.news.prodigy.com> <1111464133.508323@athnrd02>
 <423fe9df$0$11476$9b4e6d93@newsread2.arcor-online.net>
 <1111524623.705533@athnrd02>
 <4240937b$0$9215$9b4e6d93@newsread4.arcor-online.net>
 <1111568536.640808@athnrd02>
In-Reply-To: <1111568536.640808@athnrd02>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <42414d77$0$9217$9b4e6d93@newsread4.arcor-online.net>
Organization: Arcor
NNTP-Posting-Date: 23 Mar 2005 12:05:27 MET
NNTP-Posting-Host: 790d5006.newsread4.arcor-online.net
X-Trace: 
 DXC=Tc;gNgoJOknXiD6\]5e5en:ejgIfPPlddjW\KbG]kaMhdbobRQ:W=Wb?d76f1NDnTd8JM^O\[iIdc5_D:ZO]eW3g
X-Complaints-To: abuse@arcor.de
Xref: g2news1.google.com comp.lang.ada:9785 comp.lang.c++:46787
 comp.realtime:1606 comp.software-eng:5206
Date: 2005-03-23T12:05:27+01:00
List-Id: <comp.lang.ada>

Ioannis Vranos wrote:
> Georg Bauhaus wrote:
> 
>>> I forgot to say here that the cost of map's operator[] is O(log(n)) 
>>> which is fairly cheap for large amount of data.
>>
>>
>>
>> compare O(log(n)) to O(1) where n is 1, 1000, 1_000_000.
>> Make this access a part of an inner loop.
> 
> If you do the maths, you will see that log(10^6) isn't that large.

Compare log(10^6) to 1.

I can't see how O(log(n)) isn't huge when compared to
O(1), in an inner loop for containers of size 10^6.


Georg