Your answer is one click away!

Em Ae February 2016
### Reducing time complexity

I have list of objects which contains a `statusEnum`

. Now, I want to return all those objects which falls under specific list of provided statuses.

A simple solution is to loop on list of objects and then another for loop on provided list of `statusEnums`

... This would work however, It would make the time complexity of O(n)^2. Is there a way i could reduce it to O(n) ?

I can't change the map. The only other solution i could think of is maintaining another map based on statusEnums as the key but then it would increase the space complexity a lot.

**EDIT**

- I had hashMap of objects (which i said as a list)

Here is the code which i came up with for others ...

```
public List<MyObjects> getObjectsBasedOnCriteria (List<ObjectStatus> statuses, String secondCriteria){
EnumSet<ObjectStatus> enumSet = EnumSet.copyOf(statuses);
for (Map.Entry<Long, MyObject> objEntry : myObjs.entrySet()){
MyObjects obj = objEntry.getValue();
if (enumSet.contains(obj.getStatus()) && obj.equals(secondCriteria)){
...
}
}
}
```

Peter Lawrey February 2016

Assuming you have a sane number of statuses, esp if you have a enum of statuses you can use an EnumSet to match the status or a HashMap.

Even if you don't do this the time complexity is `O(n * m)`

where `n`

is the number of entries and `m`

if the number of statuses you are looking for. In general it is assumed that you will have much more records than you have statuses you are checking for.

The number of possible enum values is limited to a few thousand due to a limitation in way Java is compiled so this is always an upper bound for enums.

Andy Turner February 2016

Use an Set to hold statusEnums (probably an `EnumSet`

), and check if each instance's status is in that set using `set.contains(object.getStatus())`

, or whatever.

Lookups in `EnumSet`

and `HashSet`

are O(1), so the solution is linear (assuming just one status per object). `EnumSet.contains`

is more efficient than `HashSet.contains`

with enum values; however, the choice is irrelevant to overall time complexity.

Asked in February 2016

Viewed 2,502 times

Voted 8

Answered 2 times

Viewed 2,502 times

Voted 8

Answered 2 times