CODEWITHSUNDEEP
complexity-theorytime-complexity
chaohuang
chaohuang

Reputation: 4115

when would an O(n^2) algorithm be preferred over an O(n) algorithm?

I can think of two situations to use an O(n^2) algorithm instead of an O(n) algorithm:

  1. Because the big O notation only describes the asymptotic complexity, the exact complexity of an O(n^2) algorithm may actually be less than an O(n) algorithm when n is small.

  2. If an O(n) algorithm requires more memory space than an O(n^2) algorithm and the memory is limited, then the O(n^2) algorithm will be preferred.

Are there any other situations in favor of an O(n^2) algorithm?

Upvotes: 1

Views: 129

Answers (1)

Nate Diamond
Nate Diamond

Reputation: 5575

In cryptography, sometimes inefficient or 'unoptimized' algorithms are desired because they take similar resources (time, processing power, heat dissipated, memory used) no matter what they are processing. As such, it makes it harder to do things like timing attacks or side-channel attacks.

Upvotes: 1

Related Questions