Hi

I was wondering what the time complexity of toArray was.

Couldn't find it in the library.

thanks

Printable View

- 05-14-2012, 11:16 AMmarcosoltime complexity of toArray
Hi

I was wondering what the time complexity of toArray was.

Couldn't find it in the library.

thanks - 05-14-2012, 11:24 AMmarcosolRe: 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! - 05-14-2012, 11:27 AMk1ngRe: time complexity of toArray
Use a SortedSet, it'll already be sorted then you just use mySet.get(i);

- 05-14-2012, 11:41 AMmarcosolRe: 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.

- 05-14-2012, 11:53 AMk1ngRe: time complexity of toArray
Ah, my mistake. Wasn't paying attention. Then use a sorted set and iterate to the required index

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

- 05-14-2012, 12:03 PMk1ngRe: time complexity of toArray
Of course you should be efficient with your assignments though, i.e.

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()+"'");

- 05-14-2012, 12:27 PMmarcosolRe: 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. - 05-14-2012, 12:51 PMJosAHRe: time complexity of toArray
- 05-14-2012, 01:27 PMk1ngRe: time complexity of toArray
- 05-14-2012, 04:31 PMmarcosolRe: 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 - 05-14-2012, 04:35 PMJosAHRe: time complexity of toArray
- 05-14-2012, 04:41 PMmarcosolRe: 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 - 05-14-2012, 04:51 PMmarcosolRe: 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 - 09-19-2012, 06:51 PMsterfRe: 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).