I created integer array of different sizes and measured the running time of array creation (eg. int[] x = new int[67108864])
67108864 0.052
134217728 0.102
268435456 0.206
536870912 0.41
It is linear.
To be fair this depends on the JVM version (I have java version "1.6.0_27") and there are algorithms out there which can give you constant time but take more memory (http://eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time/)
No comments:
Post a Comment