Big O notation and Java

As we may read at wikipedia, Big_O_notation describes the evolution of functions from units to infinit. And specifically for computer science, describes the performance of algorithms and therefore resource consumption(CPU, etc.).

It is very important to understand what that means and understand the consequences of using an algorithm or another. There are algorithms that work great with small set of data but with high amounts of data they react worse.

There are two important terms: analysis of algorithms-resource usage- and computability theory-possible algorithms-.

This is the theory. let’s show two source code examples:

In case of having persons that need to be stored, there could be a problem if we what to get a specific one. Depending on the data structure used, depending on the implementation of the data structure performance changes.

Two data structures, in java, are Map or a List.

Implementation is done using Map

//<code>id</code> could be from the passport
//<code>Person</code> could be a POJO that contains the id
Map<String id, Person> persons = new HashMap<>(); 

in that case requesting a Person would be cheap and constant. That means, if we request a Person with an id, it will take one cycle, big O notation is 1:

return persons.get(id);

**TIP** We are assuming perfect Java implementation, but be careful with external libraries not that tested as the official Java implementations.

Implementation is done using List

In this case we will need to search in the list.

List<Person> persons = new ArrayList<>();

There are several options for the seach, lets use a bad one:

Person result=null;
List<Person> persons = new ArrayList<>();
for(int i=0;i>persons.size();i++){
   if(person.get(i).getId().equals(id))result=person.get(i); 
}

In this case we know that it will check all persons and as a consequence the cycles used would be n-being n the number of persons- big o notation in this case would be n.

-of course we are assuming id is unique-

Other improvements of List request

Really easy improvement would be by jumping out the loop after the person is found(break;).

Using the new Java 8 streams:

persons.stream().filter(p -> p.getId() == id)...

… or even

persons.parallelStream().filter(p -> p.getId() == id)...

would give us improvements that would not be comparable to a map implementation.

It’s good to know the technology and the solutions provided but much better never forget the principles 😉