Results 1 to 14 of 14
Thread: time complexity of toArray
 05142012, 11:16 AM #1Member
 Join Date
 Feb 2012
 Posts
 17
 Rep Power
 0
 05142012, 11:24 AM #2Member
 Join Date
 Feb 2012
 Posts
 17
 Rep Power
 0
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!
 05142012, 11:27 AM #3Member
 Join Date
 Apr 2012
 Posts
 59
 Rep Power
 0
Re: time complexity of toArray
Use a SortedSet, it'll already be sorted then you just use mySet.get(i);
 05142012, 11:41 AM #4Member
 Join Date
 Feb 2012
 Posts
 17
 Rep Power
 0
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.
 05142012, 11:53 AM #5Member
 Join Date
 Apr 2012
 Posts
 59
 Rep Power
 0
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);
 05142012, 12:03 PM #6Member
 Join Date
 Apr 2012
 Posts
 59
 Rep Power
 0
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()+"'");
 05142012, 12:27 PM #7Member
 Join Date
 Feb 2012
 Posts
 17
 Rep Power
 0
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.
 05142012, 12:51 PM #8
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,433
 Blog Entries
 7
 Rep Power
 20
Re: time complexity of toArray
cenosillicaphobia: the fear for an empty beer glass
 05142012, 01:27 PM #9Member
 Join Date
 Apr 2012
 Posts
 59
 Rep Power
 0
 05142012, 04:31 PM #10Member
 Join Date
 Feb 2012
 Posts
 17
 Rep Power
 0
Re: time complexity of toArray
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
 05142012, 04:35 PM #11
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,433
 Blog Entries
 7
 Rep Power
 20
 05142012, 04:41 PM #12Member
 Join Date
 Feb 2012
 Posts
 17
 Rep Power
 0
Re: time complexity of toArray
"Robots must be able to return the ith heaviest item they are carrying in
constant time." (a draft from my assignment)
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
 05142012, 04:51 PM #13Member
 Join Date
 Feb 2012
 Posts
 17
 Rep Power
 0
Re: time complexity of toArray
That is true. But you first said n*n*log(n) each time you add something:
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
 09192012, 06:51 PM #14Member
 Join Date
 Apr 2012
 Posts
 6
 Rep Power
 0
Similar Threads

I need help with Time Complexity???
By lulzim in forum Advanced JavaReplies: 2Last Post: 09202011, 09:11 AM 
I need help for Time Complexity of this???
By lulzim in forum Advanced JavaReplies: 9Last Post: 09162011, 03:51 PM 
Time complexity  foor loop
By hawaiifiver in forum New To JavaReplies: 5Last Post: 02052011, 04:06 PM 
time complexity questions
By myst in forum New To JavaReplies: 6Last Post: 07132010, 11:02 AM 
Time Complexity Java Code?
By Lyricid in forum New To JavaReplies: 11Last Post: 12082009, 04:27 PM
Bookmarks