Big-O notation explained by a self-taught programmer

https://justin.abrah.ms/computer-science/big-o-notation-explained.html

by maxt • 10 years ago

100 57 10 years ago

justin.abrah.ms

adsofhoads• 10 years ago

Extensively incorrect.

My company always works a "Big-O" question into interview questions. It's funny how we ask about the complexity of the algorithm and maybe 50% of applicants even know what Big-O notation is.

It doesn't seem to impact hiring decisions though. We haven't turned anyone down because they miss that question.

I think it's because anyone who has programmed for a year or so professionally already understands the concept of inefficient algorithms. They don't need to measure it mathematically, just learn how to optimize.

allan_s2• 10 years ago

I can't agree more, when interviewing I always ask this kind of questions of "theoretical knowledge" not to have the actual answer, but to see how candidates reacts when they don't know. Because if the guy not only admits he does not know directly and is eager to know what it is briefly, then you know that giving your team and environment is favorable to learning, the guy will soon be able to catch up, and it's certainly the same guy that one day will bring in the team's "tips and tricks" channel an article or an insight that will make the team's knowledge grow too.

erikbye• 10 years ago

How can anyone applying for a programming job not know Big-O notation? That's CS101. I don't care if you're self-taught, it's audacious to even call yourself a programmer if you don't know the very basics of algorithms and data structures.

If I were interviewing a candidate, and it was revealed he didn’t know Big-O notation, my next questions would be about data structures, because now I’m suspecting he wouldn’t even know how to implement the simplest of structures. What next, simple pointer arithmetic, is he unable to even walk an array?

We are no longer talking about a programmer then.

Not knowing these things, I usually chalk it up to either laziness, or lack of interest in understanding how things work.

Either way, that’s not someone I’d want on my team. Programmers should be enthusiastic about fundamentals. Good programmers have a “hacker” mentality, a need to know and understand inner workings, a craving to dig deep. I’d say this mentality is what you want from anyone in STEM.

user5994461• 10 years ago

That makes sense. Big-O notation is so overrated.

A little bit of history: C++ programmers were always able to choose the right containers simply by using this image, since long before the invention of Big-O.

http://homepages.e3.net.nz/~djm/containerchoice.png

bogomipz6• 10 years ago

"That makes sense. Big-O notation is so overrated."

Can you explain how having a classification that allows one to determine whether something is logarithmic vs vs quadratic is so overrated?

Isn't that a bit like saying "Algebra is so overrated"?

Also Donald Knuth introduced Big O somewhere around the mid 1970s and C++ didn't come along until 1979.

https://en.wikipedia.org/wiki/Big_O_notation#cite_note-knuth...

Also your link is a visualization of ADTs not run times. And while it true that ADTs are chosen for certain guarantees it still depends on how they are used in an algorithm.

Buttons840• 10 years ago

Tip: If you're asked about Big-O in an interview, and your rusty, at least determine whether the algorithm is sub-linear or super-linear. Just knowing this is 80% of what you need to be aware of in industry IMHO.

MOARDONGZPLZ• 10 years ago

Maybe you're being hyperbolic (and maybe I'm being pedantic), but from what I recall Knuth was the first to describe complexity notation in the late-60s or early-70s in The Art of Computer Programming. This definitely predates C++.

allan_s2• 10 years ago

After seeing a lot of peers being mislead by big O I think most of big O articles on the web, for the sake of clarity or simplicity omits to express one thing

if we admits functions * square_big_o O(n²) * linear_big_o O(n)

then the statement

time(squarre_big_o(x)) > time(linear_big_0(x))

is not necessary true for every value of x

because the actual complexity could be

  * 1000+1000*N
  * 2+N²

in which case most of the time you will chose the square one, because practically it will be faster.

without this in mind, you got peer who tell you that this thing is faster because the algorithm is O(n) versus O(n²), though we're talking about a function that will always have n < 10, but yesterday night they read an article about big O and now they have to throw a "let's think about the big O" remarks for every single problem we meet

Bahamut• 10 years ago

Except if one knows what the definition of big O is, there is nothing to be misled by. What big O tells you is what is the function bounded by after a constant lower bound on the input.

One always want to do performance testing to see whether it comes into play even when it comes to more practical applications such as in code.

mrcactu5• 10 years ago

Don't you want to know if your recipe takes 10 minutes or 10 hours to cook?

R_haterade4• 10 years ago

Sometimes. Sometimes you just need to throw things in the oven until the first one browns up.

I recently had a problem where I needed an adjacency matrix of shortest paths. It was a choice between dijkstra and floyd-warshall. My dijkstra implementation kicked the pants off of floyd warshall for this application by an order of magnitude, which you wouldn't really expect. And the big-O complexity was the same for both algorithms, it's just that for the graph structure, the operation count for dijkstra was much lower. It was the first one to brown up.

bogomipz6• 10 years ago

Yes and its good to know the limits of Big O as you mentioned Big O tells you what an upper bound on something is but it will provide no answer as to which to which of two algorithms with the same upper bound will be faster. There is a field that deals with this and I watched some lectures by Robert Sedgewick called "Analytic Combinatorics" where he talks about a different analysis to do just that. He talks about being able to tell large institutional clients exactly how long an algorithm on a particular input will take and how important this was in the 1970s when computing power was much slower and far more expensive.

gk1012• 10 years ago

A few comments just in case this a critical part of your program, and if running it faster would help:

1. Using a heap with Dijkstra's algorithm would speed up your program

From your comment I am guessing you are using Dijkstra's algorithm without a heap, which gives O(n * m) for one source, and O(n^2 * m) for all sources (all pairs shortest path), where n is the number of nodes/vertices, and m is the number of edges

You would be able to improve that to O(m * n * lgn) by using a heap, which improves the time to run it by quite a lot in practice

2. The time it takes to run the program also depends on the density of your matrix:

In the case where the graph is sparse: m ~ n, and will result in O(n^2 * lgn) (or O(n^3) without a heap)

In the case where the graph is dense: m ~ n^2, and will result in O(n^3 * lgn) (or O(n^4) without a heap)

Compare the numbers above to O(n^3), which is the time complexity of Floyd-Warshall

So just in terms of time complexity, Floyd-Warshall would be faster in a dense graph

hellofunk2• 10 years ago

That would be nice to know, but Big-O won't tell you that. It makes no time guarantees, it only provides an idea of an implementation. An O(1) algorithm sounds great, until you realize that 1 means 1 hour for that particular algorithm, while a competing algorithm's O(n) might mean n seconds in reality.

What's in the parenthesis is not a measure of a unit of time, which is why Big-O fanatics often miss the bigger picture.

tscs373• 10 years ago

An O(1) algorithm sounds great, until you realize that 1 means 1 hour for that particular algorithm, while a competing algorithm's O(n) might mean n seconds in reality.

Well, I'm not trying to miss the bigger picture, but if you're going to scale that your O(n) algorithm will quickly take longer than a O(1) algorithm.

I mean, let's just take a hashtable as example. This hash takes 1 hour to complete while you can search the list in milliseconds.

But what if the list has billions and billions of entries and it takes longer than 1 hour?

As some others said, Big-O is not something you use to choose one algorithm over the other, it's something you use to choose an algorithm that scales well and has acceptable performance.

O(n) vs O(1) is a rather tame comparison, what if your competing algorithm is a O(n!) or worse?

guessmyname• 10 years ago

Don't you want to know if your recipe takes 10 minutes or 10 hours to cook?

Yes, the first time, then it becomes a skill learned from experience.

I started learning Big-O a few months back and I have been working as a programmer for several years, not knowing about Big-O didn't stop me from becoming a lead of a development team. Knowing about Big-O is important but humans learn more from experience (aka. trail and error) than anything else. I started learning about Big-O just because I am interviewing right now and many tech companies love to ask those questions, but if I were not interviewing I would probably leave that topic for another time.

Anasufovic• 10 years ago

Yes, testing is critical.

e12e• 10 years ago

Rather, don't you want to know if that great dessert you ate, that took half an hour to prepare for 3 people, will be possible to make in an hour for a seating of 250 people? Because if it can't be done in an hour, you might have to pick something else to serve as dessert...

(And we could probably turn this into a question about caching, by allowing you to prepare some of it a day early...)

dizzystar• 10 years ago

As a self-taught, I always get nervous when I see articles explaining Big O because they are almost always wrong. While this one is mostly correct, it is a bit simplistic and misleading, and it could use considerable annotations. The "scary" Wikipedia article has examples that are more nuanced than what is written here; the first example shows a constant time algorithm with nested for loops.

I take issue with the math fearing throughout the article. Time complexity is math, period. There is no getting around this fact, and the sooner you accept it, the sooner you learn that the math isn't that difficult, and the sooner you realize that, without some intuition on what the math is saying, you'll never really have a firm grasp of Big O or any of the other variations.

And also, why no mention of log time?

Waterluvian2• 10 years ago

As a self taught programmer who did no math in university, the most valuable thing to me was the discovery that the math really isn't scary. Once you understand the symbols and notation, most concepts are rather easy, given you commit time to learning it.

I strayed away for so long until I watched the MIT lecture series on algorithms and it all just clicked. The best feeling was was seeing the math on the chalk board for how you determine the complexity of operations on various graph layouts and just getting it. I struggled in high school math and rarely got that feeling in class.

It was just one of those, "holy crap... It's all just an array and how we organize the data in that array that gives various benefits and drawbacks!" Incredibly empowering.

Edit: This is the series I watched: https://www.youtube.com/watch?v=HtSuA80QTyo&index=1&list=PLU...

code777777• 10 years ago

Would you please share the link to the MIT lecture series? It may help the rest of us too. Thanks!

achr22• 10 years ago

The thing I always run into when discussing big-O are people (good programmers even) who think all O(x) algorithms have the same efficiency. I find it very frustrating when someone says my streamlined O(N) algo with 5 operations has the same efficiency as their O(N) algo with 20 extra function calls and operations. Big-O is not the only determining factor...

BjoernKW• 10 years ago

In a way Big-O notation intentionally glosses over these differences. At a large scale 5 vs 20 per instance of n doesn't matter. It might matter for practical purposes but Big-O really is about making broad distinctions.

_greim_• 10 years ago

Yup. Achieving a better big-O could for example be the difference between something being possible or not, whereas fine-tuning an algo without altering its big-O might be the difference between needing five servers or ten. Still relevant, but a different class of relevance.

achr22• 10 years ago

I definitely agree with you, my comment was simply to show that there are a lot of people who use Big-O as a metric at a level where it shouldn't be applied.

castratikron• 10 years ago

Didn't know that the "O" in Big-O actually means "order". I guess it doesn't really matter too much.

If you really wanted to get theoretical, you could also talk about the whole family, including little-O, big-omega, little-omega, etc. :)

p333347• 10 years ago

The usage "big omega" and "little omega" always makes me chuckle, as they translate to "big big oh" and "little big oh".

bogomipz6• 10 years ago

I don't believe this is correct, I believe O if for Greek letter Omnicron, just as the other Greek letters are used Big Theta and Big Omega are used in discussing bounds in time complexity.

I think O meaning order would be a retronym.

Big-O notation explained by a self-taught programmer

Related Stories