# Thread: time complexity of toArray

1. Member
Join Date
Feb 2012
Posts
17
Rep Power
0

## time complexity of toArray

Hi

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

thanks

2. Member
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!

3. Member
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);

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

5. Member
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>();

int i=0;
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. Member
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>();

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

8. ## Re: time complexity of toArray

Originally Posted by marcosol
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

9. Member
Join Date
Apr 2012
Posts
59
Rep Power
0

## Re: time complexity of toArray

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

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

10. Member
Join Date
Feb 2012
Posts
17
Rep Power
0

## Re: time complexity of toArray

Originally Posted by JosAH
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. ## Re: time complexity of toArray

Originally Posted by marcosol
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

12. Member
Join Date
Feb 2012
Posts
17
Rep Power
0

## Re: time complexity of toArray

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

Originally Posted by k1ng
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. Member
Join Date
Feb 2012
Posts
17
Rep Power
0

## Re: time complexity of toArray

Originally Posted by JosAH
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:

Originally Posted by JosAH
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. Member
Join Date
Apr 2012
Posts
6
Rep Power
0

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