CODEWITHSUNDEEP
algorithmruntimebig-ocompile-time-constant
D.Life
D.Life

Reputation: 11

Choosing O(n) over O(1) when for all of n, O(1) is faster than O(n)?

Example of when I would choose O(n) algorithm over O(1) algorithm if for all of n, O(1) is faster than O(n)

Upvotes: 0

Views: 3750

Answers (2)

Arashsoft
Arashsoft

Reputation: 2757

One example is the O(1) algorithm consumes lots of memory while the O(n) one does not. And memory is more important for you compare to performance.

Upvotes: 0

superlizardmo
superlizardmo

Reputation: 333

Often, real data lends itself to algorithms with worse time complexities. For example, bubble sort, which runs in O(n^2) time is often faster on almost sorted data. Oftentimes, the constant factors might make an algorithm too slow to be practical. Remember, big-O deals with things that are more efficient in the limit, rather than in the immediate case. An algorithm that is O(1) with a constant factor of 10000000 will be significantly slower than an O(n) algorithm with a constant factor of 1 for n < 10000000.

Upvotes: 0

Related Questions