DEV Community

Discussion on: What is Big O Notation?

Collapse
 
rodiongork profile image
Rodion Gorkovenko • Edited

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.

Collapse
 
nielsenjared profile image
Jared Nielsen

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!

Collapse
 
theodesp profile image
Theofanis Despoudis

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.

Collapse
 
robconery profile image
Rob Conery • Edited

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!

Collapse
 
rodiongork profile image
Rodion Gorkovenko • Edited

Hi Rob!

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 :)

a = []
a[5] = 8
a.pop()
console.log(a.length)
Thread Thread
 
robconery profile image
Rob Conery

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.