I'm working on finding the big O for my code and I have been using a lot of Java streams to solve my problems. I was wondering how I can figure out the complexity of this code.

I'm not 100% sure, but I think that .filter and .limit has a complexity of O(1) and .sorted and .collected has a complexity of O(n).

    return robots.stream()                                                                      // start streaming the values in the list
            .filter(robot -> !robot.isBusy())                                                   // only keep the robots that aren't busy
            .sorted(Comparator.comparingDouble(robot -> robot.getLocation().dist(location)))    // sort by distance to job location
            .limit(needed)                                                                      // max out at the needed robots for the job
            .collect(Collectors.toList());                                                      // put the values into a list
}

CodePudding user response：

Stream computations heavily depend on the operation performed. If you are doing any intermediate operation(like filter and sorted),the method invocation will return almost immediately, only after scheduling the operation to be performed. When you invoke a terminal operation, the computation actually starts and the terminal operation (like forEach, collect and reduce) doesnt return until the whole process has been completed. This part takes the actual time and I am listing how much here

Filtering a stream takes O(n) time where n is the number of elements in the stream before the filtering(not after)

Sorting anything cannot be done in less than O(nlogn) computations where n is the elements in the stream)

Almost all other operations like max, min take O(n) time where n is the number of elements in the stream before the operation

Some notable exceptions are the short-circuiting ones. Takewhile and dropwhile both take time proportional to the number of elements traversed, which is, respectively, the number of elements taken, and the number of elements dropped

Limit and skip are almost constant time because they don't traverse the stream

Collect and reduce depend heavily on the operation performed.

Distinct also takes O(nlogn) time where n is the number of elements in the stream before the function was called

CodePudding user response：

Time Complexity of different methods is shown below.

1. filter → O(n), needs to check all elements
2. sorted → O(n)
3. limit → O(n), it can find Out in constant time
4. collect → O(n), needs to collect all element one by one