CODEWITHSUNDEEP
language-agnosticcomplexity-theorybig-o
jtn
jtn

Reputation: 1

Question about Big(O) performances

so my data structure class is covering time complexity and I just have a quick question about the performance for arraylist and treemap.

The get method for ArrayList is O(1) and the get method for TreeMap is o(log n)

Now, if i made a loop that iterates through the entire list or tree such as

for (int i = 0; i < blahblah.size(); i++)
{

blah blah

}

For arraylist, would this loop performance be o(1) or o(n)? I realize that when you are retrieving 1 item, the performance is O(1) but this loop goes through the entire list so wouldn't it be 1 * n items which would make it n?

Same thing with the treemap would it be o(log n) or n log n since you're going through the entire tree.

Upvotes: 0

Views: 177

Answers (4)

thomasfedb
thomasfedb

Reputation: 5983

Yes, that would be O(n). O values are almost always worst case.

Upvotes: 0

seand
seand

Reputation: 5296

"The get method for ArrayList is O(1) and the get method for TreeMap is o(log n)"

The reason ArrayList.get() is O(1) is because looking up by index is just an offset from origin. It doesn't matter if the array has 5 or 5M elements it's the same amount of work.

TreeMap.get() is O(log n) because it may have to traverse multiple elements downwards the binary tree.

Upvotes: 1

Voo
Voo

Reputation: 30226

Since you want all n elements of the data structure, the result is not just dependent of the given data structure but also of the number of elements you want to retrieve.

So yes the result would be O(n) or O(n log n), but depending on the data structure you could do better. Consider a linked list - instead of getting O(n * n) you can do just fine with O(n).

But then there's more to performance than just big O - constants do matter in reality. One example would be radix sort of 32bit numbers. O(n) for sorting sounds great, but a quick sort will be most certainly still be faster for most reasonable input sizes.

Upvotes: 1

Argote
Argote

Reputation: 2155

Going through all elements would be O(n) since you'd have to visit each at least once.

The treemap should be O(n) as well for the same reason regardles of whether you visit the nodes in postorder, inorder or preorder order.

Upvotes: -1

Related Questions