# Linked List, Array List time complexity

Printable View

• 08-18-2011, 04:04 AM
Rick99771977
Linked List, Array List time complexity
Hello i has a simple question i hope for time complexities

ArrayList: add(N / 2, x)

LinkedList: add(N / 2, x)

are these both O(log(N)) or maybe O(log(N/2))

thanks for your feedback...
• 08-18-2011, 04:13 AM
pbrockway2
Hi, welcome to the forums.

You might find you get the best help if you give your own ideas of what the time complexities might be. And say what resources you have consulted so far (the javadocs, wikipedia, etc) I say this because otherwise it might look like a homework dump.

Also, what does add(N/2,x) mean? And what is the difference between O(log(N)) and O(log(N/2))? I thought the big O notation described limiting behaviour which wouldn't be affected by the constant difference between the two expressions.
• 08-18-2011, 04:25 AM
R-J
I believe the complexity for inserting into a linked list is O(n)
• 08-18-2011, 04:31 AM
Rick99771977
ok so far i have the first 6 as

ArrayList: add(x) = O(N)
LinkedList: add(x) = O(1)
TreeSet: add(x) = O(log(N))
HashSet: add(x) = O(1)
ArrayList: add(0, x) = O(N)
LinkedList: add(0, x) = O(1)

the last two i was unsure of since they are stating is is N/2 it can't be simply O(n) since we are not using the entire N set in the list. just half of it...
• 08-18-2011, 05:37 AM
R-J
When you insert into the middle of a linked list, you are right. It's constant time (O(1)), but in order to index that place in the list it's O(n).

So in order to find its insertion place it's O(n).
Actually adding it to the list is O(1).

When you look at big O notation you ignore coefficients so O(.5n) is just O(n).