When we fetch a value from array with the index , we can do it in constant time.
eg:
var array = [3,4,56, ......]; var val = array[3]; //running time is constant Let's say we fetch a value value from an object with the property
eg:
var obj = {prop1 : 3, prop2 : 4, prop3 : 56, ......}; var val = obj.prop3; //running time? What is the running time? is it linear or constant?
Thank you in advance...
It depends on the Javascript engine used. Most JS engines implement property features as Dictionary, to support on demand creation of properties. Therefore, for most cases, it is linear. However, there are more optimized solutions, you can check the following:
We can also use
val= obj["prop3"]; Maybe it is indexed like associative arrays in php. So the running time would be constant.
EDIT : I also found this link http://www.quirksmode.org/js/associative.html talking about objects as associative arrays so they are hashed. Maybe we can say that the string (name of the object property) have a length and so the the hash would be O(n) linear but after the hash, when he have the index it'll be O(1)
We have to think more about it.
