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.

From our man in India

Man walks to the barber through rush hour traffic.  Out of 8 million ways to die, man feels like he has escaped 6 million of them.

Man has random thought on Day 5 – Is every f:@($ing family as fiercely funny as mine?

Startling notion passes through man’s head – My lime rice is better than my Mom’s. To his surprise, he is not incinerated by bolt of lightning.

Man has family in India.  Man has family in the US.  Man learns unwanted lesson – he cannot do justice to both at the same time.

Man’s Peddamma passed away in India.  She was a force of nature.  She was a pain in the ass (all forces of nature are pains in the ass).   Peddamma and Peddananna were like one of those large banyan trees, which provided shade and sustenance to a large extended family (10 aunts and uncles, 33 first cousins).  Man’s immediate family had even more special treatment.  His Dad is the youngest of the 10 siblings.  Grand Dad died early, and Peddamma and Peddananna raised his Dad to manhood.  That seamlessly extended to man’s sister and him.  Till they were about 10, they resided under his Peddamma’s stern and attentive hand.  However, for a long while now, his life and his Peddamma’s life did not intersect except for short periodic visits.  He left the protection of that banyan tree years ago.  She had been ailing for a long time.  And she was 92.  So when she finally said the big Enough, man felt reverence, and affection, but little pain.  Her passing was sad, but it was in the natural scheme of things.  It was not a tragedy.  If anything, the moment called for a celebration of her life.  My Peddamma lived a big life.

Meanwhile.  In the US.  God liberated a beloved aunt from her pain.  In return her family had to let her go.  To the Sweet Hereafter.

Process is very often, much ado about little

The first principle in the Agile Manifesto is “Individuals and Interactions, over processes and tools”. A recent development task illustrated that point starkly – skill trumps process.

Time’s a wastin ….

I was working through a weekend, exhaustively specifying the UI (mockups, WORD docs, UML State diagrams) for a recent user story, when it occurred to me that we were wasting our time.

Here is more or less the user story I was working on.

As a documentation processor, I must be able to review all of the documents in a mailbag. Upon review, I must be able to accept, or reject each of these documents.

In the time that it was taking to describe the UI to its last gory detail,  I could create a working prototype of the UI, which would be close to 80% of what the user needs.  The business folks could take the prototype for a spin, and give me feedback, which could quickly iron out the remaining 20% of the work.

See, we are building this for processors in an insurance company.   They are not looking for sophisticated, space age UI.  They just need something that is easy to understand, learn, and allows them to do the work efficiently.

Between the business analyst and me, we could have the UI squared away in a couple of weeks – a single sprint.  Add a tester if you must.

I will test every damn line of code I write anyway, before this leaves my hands.   The tester is only a second line of defense.   Even without that tester, I can get this very close to done.

So why am I specifying the UI when I can just build the thing myself?  I am having to do this because, collectively, the primary resources that are assigned to this task cannot or will not, produce an effective UI on their own.  That amazes me.  I am shaking my head as I write this.   If you have several years of experience with this problem domain, with these business analysts, with these end users, and with the same UI technology, you should be able to take the user story, fill in all the missing details, and end up at the UI.

Again, here is the user story, for reference.

As a documentation processor, I must be able to review all of the documents in a mailbag. Upon review, I must be able to accept, or reject each of these documents.

Let’s think through this.


  • Users have to review all the documents in the mail bag.
    • This means you have to list the documents to the user
  • So how do you present a list of documents.
    • A table, where each column is some attribute of the document, and each row is a document.
  • How do you make it easy for a user to study a large list of data that is in a table?
    • Allow filtering and sorting by various attributes.
    • Break up the list into several pages, and allow the user to page
      • Or simply allow the user to scroll up and down the large list.
  • How do you help the user make changes to large amounts of data safely, and correctly?
    • You must ask the user to confirm a large change.  Give her a chance to back out.
    • You must provide the user a way to undo a change.  Mistakes will happen.
  • What attributes (columns) of the documents must be included in the list
    • Leave out the attributes of the documents that are implementation-centric, which users have no need to know.
    • Pick the attributes that are business information.  Make a guess on which of these the user might be interested in.   Changing this list after review should not be hard.

Can’t the developer do this?


If you have been developing UI for any time at all, you should be able to do the analysis I just did, and arrive at a similar, if not the same place.

Business Info

You have been working in this domain for several years.  That means you must already have all the business information you need.

You must know the business-centric attributes that characterize the mailbag and documents.   These become the columns of your listing, and suggest what the user can sort and filter on.

Language and jargon that end-users will recognize must also be familiar to you by now.  This is where static labels, feedback messages and such will come from.


You have been working with your UI framework for several years.  So you should know how to implement the various UI features mentioned above – a table of data, sorting, filtering, paging, scrolling.

But none of this happened

But none of this happened, and a UI designer had to be brought in to spell everything out.   Why?

The Developer

Though they were well-versed with the UI framework, the developers have little knowledge of, or interest in, what makes an effective UI.

They are happy to be told what to build.  They want to be told what to build.  When left to their own initiative earlier, they produced a UI that so defied common sense and business reality, that the end-users’ job turned into a labor-intensive, error-prone, hell.

The Tester

If the testers know the lingua franca of the business (English, in this case), if the testers know the business, and if they know the end-users, the testers can judge if the UI satisfies the business need, simply by relying on the 2 sentence user story.

Unfortunately, testers’ familiarity with the business is uneven.  They are simply kids that compare a spec to delivered software.  If the spec is incomplete, or incorrect, these testers are thrown off course.

Further, more often than not, the testing leadership subscribes to the view that testers must only work off an exhaustively detailed spec.  Applying their own knowledge of the business, their own analytical and communication skills, is considered risky. The focus on learning the business themselves is weak.


Well, managers have all the power, which makes them responsible for everything, doesn’t it?

Who are they hiring?

The UI developer does not exhibit knowledge of effective UI design.    So how did we end up hiring him?

Say the manager that is evaluating the developer does not know anything about UI design himself.   So the manager cannot determine the developer’s competence in the matter.  That is reasonable and common.   A manager is constantly confronted with problems in which he does not have direct expertise.   Yet, she must hire people that will be responsible for solving that problem.    In that situation, a manager has to be able to recognize competence (and conversely, incompetence) as a characteristic separate from concretely observable skill.   Competence has an aura, a body language, a speech pattern, a look in the eye, as does incompetence. You have to be able to smell the bullshit before you see it.

When managers neither have concrete expertise, nor do they have a nose for fakery, we end up with these half-baked developers that require to be spoon fed.

Bad drivers

Many resources are able to learn and do more if we create the right environment.  This is usually some combination of large grained carrot and stick, coupled with the pushing of buttons that we can only learn by getting to know the resource personally.

Effective UI design for the corporate world, is a skill that can be learned by just about anyone in a few weeks, or over the course of a few UI development tasks.  If a developer has worked on UI development for going on three years, and still does not have a coherent, useful view of the matter, the leadership has been asleep at the wheel.

The same argument applies to the testers.   The management enabled them to be unthinking, ‘garbage in garbage out’ type grunts.

Skill trumps process

What a business analyst and a skilled engineer can take care, is now distributed over a whole platoon – The business analyst, the UI designer, the developer, the tester, tech and test leads to oversee the grunts, managers to oversee all of this.

Where the work could simply be a conversation between two people, now is a multi-step workflow involving many more people than that.  Two people getting a task done is just work.    Eight people, each with their own inputs, and deliverables, working on narrow parts of the whole, and that with their vision constrained by blinders, is a process.

What does the process buy us?   Nothing that I can see.  I see overhead. An 8 to 10 person team requires more management and book-keeping than a 2 person team. I see a machine with more moving parts, which exponentially increases the complexity, the amount of co-ordination required, and the number of ways the process can fail.

One or two committed, skilled engineers can replace the whole process. Why not learn to identify, hire and hold on to such resources? Why the fixation on process? Do you want get work done?  Or do you want to run a process?

Christmas, when broke

Say your purchasing power disappears.  Or say they pass a law that forbids store bought Christmas gifts.  Would you be able to fill that space under the tree?  I couldn’t.  It seems that I cannot make, or give anything, without burning cash.

Perhaps I can give people “time”.   Stick an IOU under the tree, saying something like, “Mom, I promise to spend fifteen minutes every day of the next year, cleaning the bathroom”. That is a useful gift, but rather boring.  You want gifts with a little whimsy.

I could cook.  I recently learned to bake a potato; a thrilling business.  I could wake up at 3:00 AM on Christmas morning, go out and dig fresh potatoes out of the hard winter ground, stick them in the fireplace, take them out just before the family wakes, wrap them individually in brightly colored leaves I saved from the fall … this is crazy.

The simple truth is that, if I were broke, I would not know how to participate in Christmas.

However, there may be another angle to this story.  Stipulate that no material goods must exchange hands.  Have all money changers shutdown shop for the season.  What will remain of Christmas?  Only Christ, I think.

A Christmas that is strictly a religious event, presents a different kind of challenge to folks like me, agnostic to my dying day, and multicultural, citizen of the world types, like my roommate/cousin who is arguably more religious than me (you should see him at the temple), yet is enthusiastically considering a Charlie Brown Christmas tree this year.

Interestingly, I am more comfortable with this prospect.  I don’t have to belong to your club.  If it is important to you, it is important to me, because, well, you are important to me.  I’ll wish you Merry Christmas, and happily help you celebrate Christmas.  I have some practice with this kind of thing.  Why, only a few days ago, I schlepped all the way to New Jersey for a cousin’s baby shower. Every cultural element central to a baby shower is foreign to me – motherhood, fatherhood, child birth.   What business do I have at a baby shower?   Yet, I show up, lapping up the welcome that people give me, eating the glorious food, staying out of trouble, and greasing the wheels in any way I can.  And it works.  People keep inviting me back.  I can do exactly that at Christmas, or Eid, or Hanukkah, for that matter.