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(n²) 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(n²) 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, n¹); 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, n²).

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

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

Get Go Sandwich Standoff: "The General" vs "The Rogie Hoagie"

Get Go has been KILLING it lately with crazy sandwiches that are great for advertising on the radio but I've been wondering if they're actually great for eating. The new one I've been hearing about is "The General" which is like Chinese take-out on a sesame sub roll. I hear ads for it every morning on my commute, and I see a giant billboard for it too. It's basically chicken tenders with General Tso's sauce and egg rolls on a sesame bun. I'm guessing they were inspired by Primanti's and decided to try to apply it to a different cuisine (I'm looking forward to The Russian Borscht sub which I'm sure is planned for later this summer). I ventured out to my local GetGo to try one of these out, only to be greeted by "The Rogie Hoagie" on the screen in addition to "The General." What a great surprise (and additional gastronomic challenge)! I decided to try them both and report back. "The General" only comes

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

geekitarian

Search This Blog