Skip to main content

Interview Questions: What is the Big O notation of X?

What the interviewer is really asking:
Can you figure out the computational complexity of a situation, algorithm, or process?

How to answer:
It might seem like a great idea to just memorize the Big O notation of every algorithm or process you've ever heard of, but this is going to be a lot of memorization and isn't going to be as impressive as reasoning your way through a problem.

Big O notation is simply a way to quickly describe how efficient some computing code is.  O(n) means that the process runs in time proportional to the amount of information processed; O(n2) means that the process runs in time proportional to the amount of information processed, squared.  So, for instance, if a O(n) process is processing 10,000 pieces of data, this process might take 10,000 milliseconds (or 10 seconds) assuming that each datum requires 1 millisecond of processing; a comparable O(n2) process would take over a day to process the same set of information.

An algorithm that runs a single for loop on a set of data would be O(n), because it only processes one iteration for each item (hence, n1); an algorithm that runs a for loop on a set of data, then has another for loop processing the entire set within each iteration of the first for loop, processes the entire set once for EACH item in the set (hence, n2).

A great explanation of Big O notation is available here: http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html

I've seen this question come up in about half of the jobs I've interviewed for, so it's good to be able to understand it and explain it.

Comments

Popular posts from this blog

Sheetz Sandwich Standoff: El Gringo vs Twisted Swiss

My wife left me alone for dinner tonight so I decided to check out the latest GetGo offerings... but to my great chagrin, they have no promotional subs. My travels led me to the local Sheetz, where I'd be able to keep eating the best gas station sandwiches around. To keep tradition alive, I picked the two most outrageous "Burgerz" on the menu: El Gringo and Twisted Swiss. The ingredient list is promising: Twisted Swiss is the burger with topped with swiss cheese, cole slaw, pickles, bacon, and whatever "Boom Boom Sauce" is on a pretzel bun.  El Gringo is the burger topped with pepper jack cheese, chili, Doritos, and BBQ sauce on a regular old bun. I unwrapped them both and stood back to admire the majesty before me. They're not pretty, but they do look a lot better out of the wrapper than many fast food burgers I've eaten. Twisted Swiss I expected this sandwich to be an awful mess.  It just seemed like a bunch

The Gobbler from Arby's

Stop.  Stop what you're doing and go to Arby's. Right. Now.  Have them make you a Gobbler .  This is not something you'll regret. Go. Eat this thing. Look at that bacon. Go. Arby's has a new sandwich.  It's called "The Gobbler" and as far as I can tell it's two things: a vehicle for their new deep fried turkey, and an attempt at a Thanksgiving themed sandwich.  It's also a third thing: magically delicious. move over Lucky, there's a new holiday mascot on the block Unwrapping: this actually looks like a sandwich.  It looks appetizing.  It looks like something I want to eat.  It doesn't look like the promo photo above, but it doesn't look like someone was flailing around and accidentally smashed up a sandwich, either. sexy Instagram caption goes here First bite: Wow.  I mean, "WOW."  Holy h*ck this is good.  The turkey has a really bold, meaty flavor.  It tastes a lot like turkey sliced fresh from your

A Story of Student Loan Debt

I was paying bills today and it struck me how much easier things are since my wife and I paid off all of our student loans 2 years ago.  I’m simultaneously happy with a system that allows a broke kid like me to go to a decent college, and shocked by the crushing burden of debt that it can create.  The story of my own college debt is convoluted, uninformed, and fraught with my own mistakes and missteps. I grew up in Ohio always thinking I’d be going to OSU. I ended up doing in better on my SAT than anybody expected (myself included), and the University of Dayton offered me a big scholarship. Nevermind that OSU would still have been significantly cheaper. I decided to chase the dollars. It felt great to be offered so much money, though I didn't quite grasp the idea that it was more of a discount than a cash offer. It went fine; I sometimes felt unprepared, but I did OK overall and finished the year with a decent GPA. I had a girlfriend when I started college. The long distance was t