|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Ruby |
Program 
defines the length= method of the Array class.
The length= method of the Array class provides the means
to change the size of an array at run time.
This method can be used both to increase and to decrease
the size of an array.
Program: Array class length= method.
The running time of this algorithm depends only on the new array length.
Let n be the original size of the array
and let m be the new size of the array.
Consider the case where 
.
the method first allocates an initializes a temporary array, tmp,
of size m (line 4).
This takes O(m).
At most 
elements are copied from the given array
into the temporary array (lines 5-7).
This takes 
.
The given array then is cleared by calling the clear method (line 8).
We assume that clearing an array takes O(1) time.
Next, we need to copy the values from the temporary array back
into the given array.
Before doing this, we set the item at position m-1 to nil.
This has the effect of setting the length of the given array to m
and initializing all the elements of the array to nil (line 9).
This takes O(m) time.
Finally, we copy the elements of the temporary array back into the given array.
This also takes O(m) time (lines 10-12).
Therefore, altogether the running time of the length= method is
.
Copyright © 2004 by Bruno R. Preiss, P.Eng. All rights reserved.