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 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.