Big O: what is the time complexity for this algorithm?

What is the best case and worst case time complexity for my method below?

I know ArrayList.add() is of O(1) time complexity but not sure about loaded.stream().distinct().collect(Collectors.toList());

  public static int countUnique(WordStream words) {

    ArrayList<String> loaded = new ArrayList<String>();
    ArrayList<String> empty = new ArrayList<String>();

    // Fill loaded with WordStream words
    for (String i : words) {
      loaded.add(i);
    }

    empty = (ArrayList<String>) loaded.stream().distinct().collect(Collectors.toList());

    return empty.size();
  }

Answers


You could implement this much more concisely by not using streams:

HashSet<String> loaded = new HashSet<>();
for (String i : words) {
  loaded.add(i);
}
return loaded.size();

You don't get much benefit from the parallel stream since you've got this loop being executed serially.

This approach would be O(n) also.


As noted by @Holger, if WordStream is a Collection (rather than a mere Iterable), it could be implemented even more concisely:

return new HashSet<>(words).size();

However, it is not specified in the question whether WordStream is actually a Collection.


Firstly, ArrayList() isn't O(1) for all operations, but it is for add().

distinct() is O(n), because it must examine all elements. Each iteration is O(1) because it's backed by a HashSet, which is O(1).

You could replace your code with:

return (int)loaded.parallelStream().distinct().count();

which would be a lot faster, but still O(n)


Need Your Help

Key Value storage without a file system?

mongodb key-value hard-drive document-storage

I am working on an application, where we are writing lots and lots of key value pairs. On production the database size will run into hundreds of Terabytes, even multiple Petabytes. The keys are 20 ...

Node.js: Unable to compress response using express

node.js express compression gzip http-compression

I am using express version 4.13.4 and the following code for my app.js. I have tried changing the location of app.use(compression()) which did not show any effect. when I run the application I saw no