1. Member
Join Date
Aug 2011
Posts
2
Rep Power
0

Linked List, Array List time complexity

Hello i has a simple question i hope for time complexities

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

2. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,565
Rep Power
12
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.

3. Member
Join Date
Aug 2011
Posts
11
Rep Power
0
I believe the complexity for inserting into a linked list is O(n)

4. Member
Join Date
Aug 2011
Posts
2
Rep Power
0
ok so far i have the first 6 as

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

5. Member
Join Date
Aug 2011
Posts
11
Rep Power
0
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).

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•