Interview Question – Sort the common sorting algorithms based on Big O analysis

This interview question will make me laugh. The Big O notation for sorting algorithms indeed!

Short answer; I have been a generalist application programmer for going on 20 years. In all those years, I have never had to look up a sorting algorithm’s Big O score.

If I were a systems programmer, working on a compiler, or a DBMS, I presume I would use that knowledge. Am I producing consumer software that millions of users access at the same time? Are you processing tons of data, as in social media? We may need knowledge of sorting algorithms. Build or maintain in-house business software that 300 CSRs use, on a good day? At an insurance company that is only marginally more agile than the DMV in Zootopia? Big O notation is a faint echo.

My long answer; I can tell you how I approach performance, and load handling issues, if you wish. There is much I can do before I am forced to dredge my college memories for Big O balderdash.

At Business Analysis, and Solution Design

Business says, build this. Or business says, we have a problem, do something. Parse business’ lament, and you’ll find two categories of information. Essential business requirement, and a solution that satisfies the requirement. Further, we can view the solution from two perspectives; technology agnostic, and technology-centric.

Nailing down the work in the above manner will reveal performance problems. By the same token, lack of this analysis, can make you miss performance problems.

There was once a web app. The user would push a button, which initiated an action on a bucket of 100K documents. More often than not, the action took too long to complete, and the web page would time out.

Much unhappiness ensued. Smart people tweaked the application code, and the database. It was not enough.

Finally, someone asked the right question. Shouldn’t long lived actions be asyncrhonous? The user should not have to wait at that web page till we completed the work. The system should tell the user, thanks for the work, you can go now, we’ll let you know when we finish.

Big O analysis did not raise that question.

Do you know what did? Knowing what business purpose we were trying to serve, so we could find an alternative way to get there. Courage to point out the error in system design to senior folk who allowed the error in the first place. You could also consider it, caring enough about the work to speak up. Earning the trust of the business folks and your peers in tech, so they are willing to lend you their ear. Finally some technical skills in the User Experience, and Asynchronous Processing areas.

Loose Coupling or Bust

Next, in so far as there is room for it, ensure that the parts that comprise your solution are loosely coupled. In plan English, I should be able to tinker with one part without affecting any other part. Each part must know as little as possible about the other parts. Make this happen at both large-grained and fine-grained levels.

Dave Thomas, Pragmatic Programmer, on loose coupling.

At the fine grained level, this typically puts me in Bob Martin’s Clean Code territory.

At the large grained level (aka ‘architecture’), I want to make architecture disappear. I am referring to Grady Booch’s definition of architecture.

Grady Booch's definition of Software Architecture

To paraphrase, architecture is those choices that are expensive to change. All our choices must be inexpensive to change.

Construct, Measure, Improve

Next construct the solution.

Now measure performance. Throw load at the system. Locate the bottlenecks. Remove the bottlenecks

If we got the design, and construction right, it should be easy to locate the bottlenecks. Furthermore, we can remove the inefficiency with minimal impact to the rest of the system. Remember, the parts of our solution are loosely coupled.

Improving Performance, Without the Big O

Look at I/O

About performance itself, I know one broad truth. The delays caused by disk based I/O, and network latency overwhelms anything you might do in memory.

Here are three examples from my recent experience.

Several activities in our QA environment were crawling. We noticed that log files were huge. We were at a very fine level in QA. We raised the logging level, which wrote fewer logs to disk. QA sped up to acceptable levels.

One activity was slower than acceptable in production. We discovered that we were making close to 1500 trips to the DB. We consolidated the query into 3 trips to the DB. We were good to go.

Last, we have a batch framework. It breaks a large task into small chunks, and puts the chunks on a queue. Listeners pull the chunks off the queue, and work on them in their own time. Some tasks took forever to complete, seized up even. We found that the queue choked when it received a lot of messages very fast. 750K records broken into 7500 chunks of a 100 records each, ran for 15 hours once. Increase the chunk to 20000 records, which put about 38 chunks on the queue. This worked like a charm.

In each of the above cases, I did not need Big O analysis. Someone built the Logging Framework that we used. And the DB. And the Messaging Platform. That person needed the Big O.

Learn the machine

At some point, we will need to fine tune a machine; a DB, a JVM, a CLR, a Messaging Server. For this you need in-depth specialized knowledge of the particular machine. I don’t have that. Remember, I am a generalist. I know what questions to ask. I can dig up answers. And then forget, because I don’t use that knowledge everyday.

More to this than we can see

Last, at this level, there are often a lot of variables, which interact in ways that is not always easy to predict. For instance, there are tons of JVM parameters, and DB switches. You do what you need to do to get past the current problem. Then you watch how things go, till you have to intervene again.

This is what I know about performance.

See, I don’t remember enough Big O analysis to save my life. Yet, life goes on.