liveBook · Manning

Quadratic time complexity

As explained in Vibe Engineering

Quadratic time complexity is an algorithmic growth rate in which running time increases proportionally to the square of input size.

Quadratic time complexity means runtime grows as O(N²). A hidden repeated scan can make apparently concurrent code catastrophically slow: calling indexOf inside a grouping operation scans the list for every account. section 7.1.2

Concurrency that loses to repeated scanning

With 10,000 accounts, the indexOf-based grouping performs tens of millions of redundant comparisons. A custom benchmark measured concurrent execution at 30,398 ms, compared with 25 ms for the single-threaded version. section 7.1.2

Cursor
public Optional<Account> accountParallel(Integer id) {
        return accounts.parallelStream().filter(v -> v.getId().equals(id)).findAny(); #A
   }
private final ExecutorService executor =
    Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
public Optional<Account> accountConcurrent(Integer id) { #B
        int chunkSize = Math.max(1, accounts.size() /
Runtime.getRuntime().availableProcessors());
        List<CompletableFuture<Optional<Account>>> futures =
                accounts.stream()
                        .collect(Collectors.groupingBy(account ->
accounts.indexOf(account) / chunkSize))
                        .values()
                        .stream()
                        .map(chunk -> CompletableFuture.supplyAsync(() ->
                                chunk.stream().filter(v ->
v.getId().equals(id)).findAny(), executor))
                        .collect(Collectors.toList());
        return futures.stream()
                .map(CompletableFuture::join)
                .filter(Optional::isPresent)
                .findFirst()
                .orElse(Optional.empty());
    }
  public Optional<Account> accountOptimized(Integer id) { #C
      ForkJoinPool customThreadPool = new
ForkJoinPool(Runtime.getRuntime().availableProcessors());
        try {
            return customThreadPool.submit(() ->
                    accounts.parallelStream().filter(v ->
v.getId().equals(id)).findAny()).get();
        } catch (Exception e) {
            throw new RuntimeException("Error in parallel processing", e);
        } finally {
            customThreadPool.shutdown();
        }
}
    public List<Optional<Account>> findMultipleAccounts(List<Integer> ids) {
#D
        return ids.parallelStream()
                .map(this::accountParallel)
                .collect(Collectors.toList());
    }

Inspect the accountConcurrent implementation to see how indexOf inside groupingBy introduces the repeated scan. section 7.1.2

How Vibe Engineering covers it

How deep it goes
Traces O(N²) to repeated list scans and quantifies redundant comparisons, without developing formal complexity analysis.
Examples
Uses indexOf inside groupingBy, 10,000-account data, and benchmark results contrasting single-threaded, parallel, concurrent, and optimized methods.
What it assumes
Assumes familiarity with Java lists, streams, groupingBy, and basic performance benchmarking.
What you can do after
Diagnose quadratic bottlenecks before trusting concurrency improvements or benchmark results.
How it connects
Connects algorithmic complexity with concurrency, parallel streams, benchmarking, and JMH.

Also explained in

Compare how 7 books explain quadratic time complexity →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Vibe Engineering. The section links point to the parts of the book it draws on.