Hi Jared! Honestly, I'm not sure JavaScript is good choice to discuss O-notation and time complexity.
Arrays in JavaScript are not just plain arrays. Depending on implementation they have hastable inside and, probably, not only this. I do believe access is still O(1) "amortized", but it may be funny to try inventing test-case for which it doesn't hold.
Hi Rodion! Thanks for your reply and thanks for the idea for a future post. An article about array implementation in JavaScript would be both fun to write and useful for the community. As suggested by the title, this post is intended for beginners and beginners on this platform are likely using JavaScript. The examples are used to illustrate fundamental concepts. The points you are making require deeper understanding of Big O, data structures, and JavaScript itself. Gotta start somewhere! I think this post is a good place to do just that. Cheers!
True. If you assign a different unit-cost for each operation based on the lower implementation details you might get surprised of how different complexities can you get. If we assume a simple model though it's easier to comprehend.
Founder of Big Machine and Tekpub. Author of The Imposter’s Handbook, creator of This Developer's Life, method speaker and Azure Developer[0] at @microsoft
Hi Rodion - I think there's some confusion and I'd like to see if I can help clear it up :).
Arrays in JavaScript are not just plain arrays
If you mean that there aren't pointers in memory - yes! True. They can also act like stacks/queues depending on how you use them. The thing is: whether they're an array or not is beside the point when you're discussing Big-O. The big thing is: are they iterable? And indeed they are. That makes their use in these examples ideal
Arrays might be collections of objects (hash tables, as you suggest) but that doesn't change the nature of the array. You still need to access the array by index as Jared has done, or you need to iterate.
Access to an array is only O(1) if you know the index and it's completely independent of what's inside the array. Either way - using JS is just fine for Jared's examples. The simpler the better!
Access to an array is only O(1) if you know the index
I'm not sure you can find any words in specification of JS that any JS engine is required to implement them in this way :)
E.g. there probably is no guarantee that they are not implemented as RB-trees inside. Or that current implementation (say in Chrome 80) which is based on hashtable (not sure) won't change to tree in Chrome 81.
I meant just that. JS arrays are really queer and their behavior for certain operation may differ, say, between V8 engine and Rhino :)
Founder of Big Machine and Tekpub. Author of The Imposter’s Handbook, creator of This Developer's Life, method speaker and Azure Developer[0] at @microsoft
True the implementation details aren’t on the top of my head and I totally agree it’s a weird language. Wouldn’t surprise me to find out that really, under the hood, it’s a mess. Either way Big O doesn’t care mate. That stuff (Lang or framework details) is actually beside the point. An array, as a data structure, is treated as O(1) conceptually speaking as that’s where we are... in the land of concepts.
There is a concern with true measurement (I think it’s big T or something) but Big O is meant as shorthand... like and algorithmic pronoun.
I think this is just as important a point as any other and usually where people get stuck with Big O... the “what if my input is..” or “what if I’m using X which doesn’t have Y concern”. All of those are valid! But Big O is a bit more generalized in that sense.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Hi Jared! Honestly, I'm not sure
JavaScript
is good choice to discussO-notation
and time complexity.Arrays in JavaScript are not just plain arrays. Depending on implementation they have hastable inside and, probably, not only this. I do believe access is still
O(1)
"amortized", but it may be funny to try inventing test-case for which it doesn't hold.Hi Rodion! Thanks for your reply and thanks for the idea for a future post. An article about array implementation in JavaScript would be both fun to write and useful for the community. As suggested by the title, this post is intended for beginners and beginners on this platform are likely using JavaScript. The examples are used to illustrate fundamental concepts. The points you are making require deeper understanding of Big O, data structures, and JavaScript itself. Gotta start somewhere! I think this post is a good place to do just that. Cheers!
True. If you assign a different unit-cost for each operation based on the lower implementation details you might get surprised of how different complexities can you get. If we assume a simple model though it's easier to comprehend.
Hi Rodion - I think there's some confusion and I'd like to see if I can help clear it up :).
If you mean that there aren't pointers in memory - yes! True. They can also act like stacks/queues depending on how you use them. The thing is: whether they're an array or not is beside the point when you're discussing Big-O. The big thing is: are they iterable? And indeed they are. That makes their use in these examples ideal
Arrays might be collections of objects (hash tables, as you suggest) but that doesn't change the nature of the array. You still need to access the array by index as Jared has done, or you need to iterate.
Access to an array is only O(1) if you know the index and it's completely independent of what's inside the array. Either way - using JS is just fine for Jared's examples. The simpler the better!
Hi Rob!
I'm not sure you can find any words in specification of JS that any JS engine is required to implement them in this way :)
E.g. there probably is no guarantee that they are not implemented as RB-trees inside. Or that current implementation (say in Chrome 80) which is based on hashtable (not sure) won't change to tree in Chrome 81.
I meant just that. JS arrays are really queer and their behavior for certain operation may differ, say, between V8 engine and Rhino :)
True the implementation details aren’t on the top of my head and I totally agree it’s a weird language. Wouldn’t surprise me to find out that really, under the hood, it’s a mess. Either way Big O doesn’t care mate. That stuff (Lang or framework details) is actually beside the point. An array, as a data structure, is treated as O(1) conceptually speaking as that’s where we are... in the land of concepts.
There is a concern with true measurement (I think it’s big T or something) but Big O is meant as shorthand... like and algorithmic pronoun.
I think this is just as important a point as any other and usually where people get stuck with Big O... the “what if my input is..” or “what if I’m using X which doesn’t have Y concern”. All of those are valid! But Big O is a bit more generalized in that sense.