Results 1 to 5 of 5
  1. #1
    Rick99771977 is offline Member
    Join Date
    Aug 2011
    Posts
    2
    Rep Power
    0

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

  2. #2
    pbrockway2 is online now Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,574
    Rep Power
    12

    Default

    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. #3
    R-J
    R-J is offline Member
    Join Date
    Aug 2011
    Posts
    11
    Rep Power
    0

    Default

    I believe the complexity for inserting into a linked list is O(n)

  4. #4
    Rick99771977 is offline Member
    Join Date
    Aug 2011
    Posts
    2
    Rep Power
    0

    Default

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

  5. #5
    R-J
    R-J is offline Member
    Join Date
    Aug 2011
    Posts
    11
    Rep Power
    0

    Default

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

Similar Threads

  1. Array to Linked List
    By Aiquoc in forum New To Java
    Replies: 2
    Last Post: 04-23-2011, 02:32 PM
  2. Replies: 4
    Last Post: 02-21-2011, 10:34 AM
  3. Replies: 1
    Last Post: 12-03-2009, 08:03 AM
  4. How to link a Array elemant to a Linked list Node
    By ravinda in forum New To Java
    Replies: 2
    Last Post: 04-18-2009, 10:16 AM
  5. linked list or array?
    By sick_peng in forum New To Java
    Replies: 6
    Last Post: 04-15-2009, 08:33 PM

Posting Permissions

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