Results 1 to 14 of 14
  1. #1
    marcosol is offline Member
    Join Date
    Feb 2012
    Posts
    17
    Rep Power
    0

    Default time complexity of toArray

    Hi

    I was wondering what the time complexity of toArray was.
    Couldn't find it in the library.


    thanks

  2. #2
    marcosol is offline Member
    Join Date
    Feb 2012
    Posts
    17
    Rep Power
    0

    Default Re: time complexity of toArray

    Just found out that it will be O(n). Not sure if its correct. Time Complexity of HashMap.toArray() (Java in General forum at JavaRanch)
    But if it is i've got another problem.
    I have a set of Item objects, the assignment said it had to be a set, and I have to provide a method to return the ith heaviest Item in ct time. I thought the only way to do so is making sure my items set is a sorted one. So my Item class implements comparable and the compareTo compares the weight of items. But a there is no set that provides a method to retrieve the ith item in the set. So I thought of toArray but it appears not to be in ct time. Any ideas. Thanks!

  3. #3
    k1ng is offline Member
    Join Date
    Apr 2012
    Posts
    59
    Rep Power
    0

    Default Re: time complexity of toArray

    Use a SortedSet, it'll already be sorted then you just use mySet.get(i);

  4. #4
    marcosol is offline Member
    Join Date
    Feb 2012
    Posts
    17
    Rep Power
    0

    Default Re: time complexity of toArray

    Ow i did not know you could use .get(i) on a set. Just to be curious but from what super class or interface does the support of .get(i) comes from? Cause I can't find it.

  5. #5
    k1ng is offline Member
    Join Date
    Apr 2012
    Posts
    59
    Rep Power
    0

    Default Re: time complexity of toArray

    Ah, my mistake. Wasn't paying attention. Then use a sorted set and iterate to the required index

    Java Code:
        int requiredIndex = 2;
        SortedSet<String> set = new TreeSet<String>();
        set.add("b");
        set.add("a");
        set.add("c");
        set.add("d");
    
        int i=0;
        String valueAtIndex = "<not found>";
        for (String s : set)
        {
          System.out.println("Testing '"+s+"' @ "+i);
          if (i==requiredIndex)
          {
            valueAtIndex = s;
            break;
          }
          else
          {
            System.out.println("Value isn't '"+s+"'");
            i++;
          }
        }
        
        System.out.println(valueAtIndex);

  6. #6
    k1ng is offline Member
    Join Date
    Apr 2012
    Posts
    59
    Rep Power
    0

    Default Re: time complexity of toArray

    Of course you should be efficient with your assignments though, i.e.

    Java Code:
        int requiredIndex = 2;
        SortedSet<String> set = new TreeSet<String>();
        set.add("b");
        set.add("a");
        set.add("c");
        set.add("d");
    
        int i=0;
        Iterator it = set.iterator();
        while (i<requiredIndex && it.hasNext())
        {
         it.next();
          i++;
        }
        ;
        
        System.out.println("Value at "+i+" '"+(String)it.next()+"'");

  7. #7
    marcosol is offline Member
    Join Date
    Feb 2012
    Posts
    17
    Rep Power
    0

    Default Re: time complexity of toArray

    hey thanks buddy, really nice of you. But i do need a ct time solution.
    I just reread my assignment and it said .getItems() should return a set, they do not specifically say items has to be a saved as a set. So I 'm going to save it as a List and use Collections.sort() whenever I add an Item. Then getItems() will be something like return new HashSet(ItemsList). Might not be the nicest way but I respect the assignment. Better ideas are still welcome.

  8. #8
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,005
    Blog Entries
    7
    Rep Power
    20

    Default Re: time complexity of toArray

    Quote Originally Posted by marcosol View Post
    So I 'm going to save it as a List and use Collections.sort() whenever I add an Item.
    Yuck; sorting takes O(n*log(n)) operations for a collection of n items; when you sort the entire thing each time you add an element you have to do O(n*n*log(n)) operations.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  9. #9
    k1ng is offline Member
    Join Date
    Apr 2012
    Posts
    59
    Rep Power
    0

    Default Re: time complexity of toArray

    Quote Originally Posted by marcosol View Post
    hey thanks buddy, really nice of you. But i do need a ct time solution.
    ct time?

    Quote Originally Posted by marcosol View Post
    .getItems() should return a set,
    I thought you had to return one item from the set, not the whole set?!

  10. #10
    marcosol is offline Member
    Join Date
    Feb 2012
    Posts
    17
    Rep Power
    0

    Default Re: time complexity of toArray

    Quote Originally Posted by JosAH View Post
    Yuck; sorting takes O(n*log(n)) operations for a collection of n items; when you sort the entire thing each time you add an element you have to do O(n*n*log(n)) operations.

    kind regards,

    Jos
    How do you get at n*n*log(n)? There is one list.add() in the code(ct time) and one Collections.(merge)sort() (n * log(n)) So each time you add something will still be n log(n) no?

    I could write an insertion sort myself so that the sorting complexity would be just n since whenever I add something the list will already be fully sorted.
    But it does not change the fact that retrieving the ith heaviest item will happen in cte time. The assignment says nothing about complexity adding an item.

    greets

  11. #11
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,005
    Blog Entries
    7
    Rep Power
    20

    Default Re: time complexity of toArray

    Quote Originally Posted by marcosol View Post
    So each time you add something will still be n log(n) no?
    Yup, and you're inserting (and sorting) something n times so that makes O(n*n*log(n)).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  12. #12
    marcosol is offline Member
    Join Date
    Feb 2012
    Posts
    17
    Rep Power
    0

    Default Re: time complexity of toArray

    Quote Originally Posted by k1ng View Post
    ct time?
    "Robots must be able to return the ith heaviest item they are carrying in
    constant time." (a draft from my assignment)



    Quote Originally Posted by k1ng View Post
    I thought you had to return one item from the set, not the whole set?!
    They are going to run some tests on the program and therefore it is necessary that I implement given methods of a given type in my code.
    I first thought when they say I should have a method public Set<Item> getItems(), I had to save the items collection as a set.
    But I just need a method that returns a set( this is about a totally different method then the one above but is just the reason why I thought I was obliged to use a set)

    Sorry if I was not clear earlier.

    greets

  13. #13
    marcosol is offline Member
    Join Date
    Feb 2012
    Posts
    17
    Rep Power
    0

    Default Re: time complexity of toArray

    Quote Originally Posted by JosAH View Post
    Yup, and you're inserting (and sorting) something n times so that makes O(n*n*log(n)).
    That is true. But you first said n*n*log(n) each time you add something:

    Quote Originally Posted by JosAH View Post
    Yuck; sorting takes O(n*log(n)) operations for a collection of n items; when you sort the entire thing each time you add an element you have to do O(n*n*log(n)) operations.
    Those are two different things no? And I think this is not really applicable to my project cause you only add one thing at a time(whenever a robot picks up something).
    I do agree this is most inefficient if you want you add a bunch of items at once.

    greets

  14. #14
    sterf is offline Member
    Join Date
    Apr 2012
    Posts
    6
    Rep Power
    0

    Default Re: time complexity of toArray

    "Robots must be able to return the ith heaviest item they are carrying in
    constant time."
    OK so let them sort the items while they are carrying them. Once they have reached the goal they return the i-th in constant time (simply the i-th object).

Similar Threads

  1. I need help with Time Complexity???
    By lulzim in forum Advanced Java
    Replies: 2
    Last Post: 09-20-2011, 09:11 AM
  2. I need help for Time Complexity of this???
    By lulzim in forum Advanced Java
    Replies: 9
    Last Post: 09-16-2011, 03:51 PM
  3. Time complexity - foor loop
    By hawaiifiver in forum New To Java
    Replies: 5
    Last Post: 02-05-2011, 04:06 PM
  4. time complexity questions
    By myst in forum New To Java
    Replies: 6
    Last Post: 07-13-2010, 11:02 AM
  5. Time Complexity Java Code?
    By Lyricid in forum New To Java
    Replies: 11
    Last Post: 12-08-2009, 04:27 PM

Tags for this Thread

Posting Permissions

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