From: Eric Hodel <drbrain@...7.net>
Date: 2005-04-23T09:44:04+09:00
Subject: Re: Question: Time efficiency of Array <<

--Apple-Mail-8-618338431
Content-Transfer-Encoding: 7bit
Content-Type: text/plain; charset=US-ASCII; format=flowed

On 22 Apr 2005, at 17:31, Peter Suk wrote:

> Forgive the newbie-ish question.  I have been playing around with 
> Array, and discovered the << operator:
>
> irb(main):001:0> array = [1, 2, 3, 4]
> => [1, 2, 3, 4]
> irb(main):002:0> array2 = array << 5
> => [1, 2, 3, 4, 5]
> irb(main):003:0> array
> => [1, 2, 3, 4, 5]
> irb(main):004:0> array2
> => [1, 2, 3, 4, 5]
> irb(main):005:0>
>
> I am curious about the time & space complexity of n << operations to 
> an array.  Is it O(n^2) or is it O(n)?  Is there a doubling of 
> allocated space going on behind the scenes?

Take a look at rb_ary_store in array.c...

It looks like an Array grows by half of its current capacity when an 
index is larger than the current capacity, but by no less than 
ARY_DEFAULT_SIZE (16 elements).


-- 
Eric Hodel - drbrain@segment7.net - http://segment7.net
FEC2 57F1 D465 EB15 5D6E  7C11 332A 551C 796C 9F04

--Apple-Mail-8-618338431
content-type: application/pgp-signature; x-mac-type=70674453;
	name=PGP.sig
content-description: This is a digitally signed message part
content-disposition: inline; filename=PGP.sig
content-transfer-encoding: 7bit

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (Darwin)

iEYEARECAAYFAkJpmjAACgkQMypVHHlsnwQxsQCdFv0GFoCMDfaDY9OFS65jQQ9P
uWwAnRvS/Z4PYx0S41BlKJ5I/YyP5xaQ
=R+pV
-----END PGP SIGNATURE-----

--Apple-Mail-8-618338431--