The Blog of Ian Mercer.

10 reasons my O(n²) algorithm is better than your O(n) algorithm

OK, so it's a controversial title, but the point I want to make is that programmers often get confused about the time complexity, i.e. order O() of an algorithm and performance.  They will happily declare that their O(n) algorithm is so much better than someone else's O(n²) algorithm as they rip out some simple, stable, working code and replace it with their vastly more complex, un-tested, but 'optimized' code, often without even measuring to see if there is in fact any performance gain.  The fact is that O() notation refers to the asymptotic performance of an algorithm and that in a typical environment with typical data you aren't going to be anywhere close to asymptotic behavior.  Performance is, in fact, influenced by many other factors besides the time complexity of an algorithm.

So what factors can make an O(n²) algorithm better than an O(n) algorithm?

​1. It might take a very large N before the O(n²) algorithm is slower than the O(n) algorithm.  And we aren't talking n=10, n=100, ... here, but perhaps millions or billions before the cross-over in performance is achieved.

​2. O() refers to time-complexity not to how long the algorithm actually takes to execute on a particular CPU.  For that you need to look at the mix of instructions used and how long each of those instructions takes.  But that in itself is a gross-simplification as we shall see next ...

Even if the two algorithms have a very similar number of operations using similar CPU instructions, they still are not going to run at the same speed:

​3. The compiler might be able to apply optimizations to one algorithm that it cannot apply to the other, dramatically boosting performance.

​4. The CPU itself might be able to optimize the instruction execution sequence through pipelining or other techniques to dramatically boost performance.  A dumb scan of an array for example can be accomplished really quickly by most CPUs because they have been optimized to handle such frequent, repetitive tasks.

​5. A simpler O(n²) algorithm might have tighter loops in it than the more-complex O(n) algorithm allowing it to run entirely in on-chip memory, dramatically boosting performance.

Even if two algorithms have similar operations and similar raw CPU performance they may have different space requirements.  The O(n) algorithm might require 10x as much data space to run or maybe a different order of space requirement to the other, e.g. O(n²) space requirement vs O(n) space requirement.

​6. The algorithm that requires least data space in the inner loop may find that its data is being held in registers or on-chip RAM during execution and thus receive a significant performance boost.

​7. The more space hungry algorithm might have its data paged to disk during operation incurring a huge additional time penalty.

Some algorithms are inherently more parallelizable than others:

​8. As we move to a world of multi-core processors it's going to be more important to be able to parallelize code to get performance gains of 4x, 8x, ... PLINQ and other parallel extensions in modern languages can easily be applied to 'dumb' nested for-loops to gain significant improvements in performance.  Applying those same speedups to your 'optimized' tree-based code might be much harder or even impossible.

'Better' is a very subjective word, better performance is just one of many issues

​9. The better algorithm is probably the one that's easiest to write, easiest for others to read, easiest to test and easiest to maintain.  A simple nested for-loop may be 1000x better than some O(n) algorithm when best is defined like this.

​10. Even if your algorithm beats mine with all of these factors taken into account that's no guarantee it will do so in the future.  Compilers evolve, CPUs get smarter and much of that effort is devoted to making dumb code faster.

Conclusion

Premature optimization is always a bad idea.

Many 'optimizations' can actually lead to worse not better performance.

Always measure, then optimize, then measure again.

It's often cheaper to buy another server than it is to have someone 'optimize' your code.

O(n) is a much misunderstood topic

On modern servers space complexity is nearly always more important than time complexity these days.  If you can run in on-chip RAM you have a huge advantage.


Related Stories

My love/hate relationship with Stackoverflow

Stackoverflow is a terrific source of information but can also be infuriating.

Ian Mercer
Ian Mercer

Xamarin Forms Application For Home Automation

Building a Xamarin Forms application to control my home automation system

Ian Mercer
Ian Mercer

JSON Patch - a C# implementation

Ian Mercer
Ian Mercer

Websites should stop using passwords for login!

A slightly radical idea to eliminate passwords from many of the websites you use just occasionally

Ian Mercer
Ian Mercer

Dynamically building 'Or' Expressions in LINQ

How to create a LINQ expression that logically ORs together a set of predicates

Ian Mercer
Ian Mercer

VariableWithHistory - making persistence invisible, making history visible

A novel approach to adding history to variables in a programming language

Ian Mercer
Ian Mercer

Neo4j Meetup in Seattle - some observations

Some observations from a meetup in Seattle on graph databases and Neo4j

Ian Mercer
Ian Mercer

Updated Release of the Abodit State Machine

A hierarchical state machine for .NET

Ian Mercer
Ian Mercer

My first programme [sic]

At the risk of looking seriously old, here's something found on a paper tape

Ian Mercer
Ian Mercer

Building a better .NET State Machine

A state machine for .NET that I've released on Nuget

Ian Mercer
Ian Mercer

The Internet of Dogs

Connecting our dog into the home automation

Ian Mercer
Ian Mercer

A simple state machine in C#

State machines are useful in many contexts but especially for home automation

Ian Mercer
Ian Mercer

Convert a property getter to a setter

Ian Mercer
Ian Mercer

MongoDB Map-Reduce - Hints and Tips

Ian Mercer
Ian Mercer

Weather Forecasting for Home Automation

Ian Mercer
Ian Mercer

Lengthening short Urls in C#

Ian Mercer
Ian Mercer

Why don't you trust your build system?

Ian Mercer
Ian Mercer

ASP.NET MVC SEO - Solution Part 1

Ian Mercer
Ian Mercer

Elliott 803 - An Early Computer

Ian Mercer
Ian Mercer

Building sitemap.xml for SEO ASP.NET MVC

Ian Mercer
Ian Mercer

Continuous Integration -> Continuous Deployment

What is "quality" in terms of a released software product or website?

Ian Mercer
Ian Mercer

Making a bootable Windows 7 USB Memory Stick

Here's how I made a bootable USB memory stick for Windows 7

Ian Mercer
Ian Mercer

Tip: getting the index in a foreeach statement

A tip on using LINQ's Select expression with an index

Ian Mercer
Ian Mercer

SQL Server - error: 18456, severity: 14, state: 38 - Incorrect Login

A rant about developers using the same message for different errors

Ian Mercer
Ian Mercer

WCF and the SYSTEM account

Namespace reservations and http.sys, my, oh my!

Ian Mercer
Ian Mercer

404 errors on IIS6 with ASP.NET 4 Beta 2

Ian Mercer
Ian Mercer

Mixed mode assembly errors after upgrade to .NET 4 Beta 2

Fixing this error was fairly simple

Ian Mercer
Ian Mercer

The EntityContainer name could not be determined

How to fix the exception "the entitycontainer" name could not be determined

Ian Mercer
Ian Mercer

Shortened URLs should be treated like a Codec ...

Expanding URLs would help users decide whether or not to click a link

Ian Mercer
Ian Mercer

Tagging File Systems

Isn't it time we stopped knowing which drive our file is on?

Ian Mercer
Ian Mercer

A great site for developing and testing regular expressions

Just a link to a site I found useful

Ian Mercer
Ian Mercer

Introducing Jigsaw menus

A novel UI for menus that combines a breadcrumb and a menu in one visual metaphor

Ian Mercer
Ian Mercer

Entity Framework in .NET 4

Ian Mercer
Ian Mercer

Fix for IE's overflow:hidden problem

Ian Mercer
Ian Mercer

A better Tail program for Windows

A comparison of tail programs for Windows

Ian Mercer
Ian Mercer

Measuring website browser performance

Found this great resource on website performance

Ian Mercer
Ian Mercer

Shaving seconds off page load times

Ian Mercer
Ian Mercer

Amazon Instance vs Dedicated Server comparison

Some benchmark performance for Amazon vs a dedicated server

Ian Mercer
Ian Mercer

System.Data.EntitySqlException

Hints for dealing with this exception

Ian Mercer
Ian Mercer

Agile Software Development is Like Sailing

You cannot tack too often when sailing or you get nowhere. Agile is a bit like that.

Ian Mercer
Ian Mercer

Exception Handling using Exception.Data

My latest article on CodeProject covers the lesser known Exception.Data property

Ian Mercer
Ian Mercer

Javascript error reporting

Sending client-side errors back to a server for analysis

Ian Mercer
Ian Mercer

AntiVirus Software is the Worst Software!

When your anti-virus software starts stealing your personal data, it's time to remove it!

Ian Mercer
Ian Mercer

ASP.NET Custom Validation

How to solve a problem encountered with custom validation in ASP.NET

Ian Mercer
Ian Mercer

Optimization Advice

Some advice on software optimization

Ian Mercer
Ian Mercer

Linq's missing link

LinqKit came in handy back in 2009

Ian Mercer
Ian Mercer

Google Chart API

Ian Mercer
Ian Mercer

Cache optimized scanning of pairwise combinations of values

Using space-filling curves to optimize caching

Ian Mercer
Ian Mercer

Threading and User Interfaces

A rant about how few software programs get threading right

Ian Mercer
Ian Mercer

Take out the trash!

Why Windows shutdown takes so long

Ian Mercer
Ian Mercer

Dell upgrades - a pricey way to go

Ian Mercer
Ian Mercer

Programming mostly C#

Ian's advice on programming

Ian Mercer
Ian Mercer