basically the title.
#how does indexing in a dynamic array take O(1) time if you have to iterate through the array?
fringe pewter
fallen harness
Dynamic array? If you're iterating it's O(n), it's only O(1) if it's a mapping like in a hash map
fringe pewter
So iterating is O(n) but indexing itself is O(1)?
fallen harness
Indexing would be O(1) if it's a direct mapping to memory
warm gate
When you say "indexing", I assume you mean accessing a single element at a specified index. If not, please correct me. Dynamic arrays are still allocated contiguously in memory. When you go to access an element, that index is treated as a memory offset just as in a statically allocated array.
If that is not what you meant, please clarify
fallen harness
(it's a bit confusing that you tagged this as "other" and didn't mention a language)
fringe pewter
Well it's not really a language. It came up in data structures and algorithms course
fringe pewter
When you say "indexing", I assume you mean accessing a single element at a speci...
Yea I think this is what I mean
warm gate
Yea I think this is what I mean
Accessing an element in an array is always going to be O(1) because it's just a single jump to that memory address from the memory address identifying the start of your array
fringe pewter
Accessing an element in an array is always going to be O(1) because it's just a ...
Great thanks.
Another question, is how did went from n/2 to m/4. I'm not understanding the math here. Because let's say n=6, and after 12/2 removals we resize down the array to 6, how does it become m/4. since 12/4 =3
warm gate
that's what I took from it lol
devout fulcrum
Accessing an element in an array is always going to be O(1) because it's just a ...
This of course, depends on how the array is implemented. But typically it will be direct memory access and if not it'll be in some sort of linked list kinda thing which will be O(n)
warm gate
This of course, depends on how the array is implemented. But typically it will b...
Yeah, but the array primitive will have contiguous memory, otherwise I wouldn't really say it's an array lol - but that's just semantics
devout fulcrum
Agreed
fringe pewter
They defined m to be 2n
oooo I see. so basically what they're saying is that after n/2 or m/4 elements are removed, we can finally resize the array down
devout fulcrum
I think so, but I think it also depends on the growth factor
Don't quote me on any of this, I never actually properly learned this stuff lol
warm gate
I would have to watch through more of that video for more context on the things he's actually referring to, but I don't have time to do so at the moment
devout fulcrum
Yeah neither do I
fringe pewter
he doesn't really go more in detail. the next few minutes was just another way to create a data structure that can have O(1) indexing and amortized O(1) insert/deletion
warm gate
I think a lot of data structures are more practical to learn in the context of algorithms they're useful in
an array is a very primitive type so learning it generally makes more sense
but there are a lot of other data types that are good for very specific cases
fringe pewter
i haven't gotten into any algorithms yet. I just learned about ADTs like a list and set and then we finally got into the data structures like linked list and dyanmic array