Big-O notation explained by a self-taught programmer • Hacker News Board

Re: Big-O notation explained by a self-taught programmer

#11

Post by user5994461 » Sat, Oct 29, 2016, 4:04 PM UTC

c0achmcguirk wrote: post #3

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 i…

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

Re: Big-O notation explained by a self-taught programmer

#12

Post by bogomipz » Sat, Oct 29, 2016, 4:17 PM UTC

user5994461 wrote: post #11

c0achmcguirk wrote: post #3

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 i…

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

> "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.

Re: Big-O notation explained by a self-taught programmer

#13

Post by dizzystar » Sat, Oct 29, 2016, 4:19 PM UTC

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?

Re: Big-O notation explained by a self-taught programmer

#14

Post by binarycrusader » Sat, Oct 29, 2016, 4:19 PM UTC

erikbye wrote: post #9

allan_s wrote: post #5

Earlier quoted context omitted.

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 certa…

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…

How can anyone applying for a programming job not know Big-O notation? That's CS101.

You pointed out exactly how someone would not know -- they may have never taken computer science classes and taught themselves programming.

Or they may have taken some CS classes, not enough to have covered that particular concept.

I'd guess that, especially for older programmers, anecdotally, it's not uncommon to not really understand or use it.

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.

Just because someone doesn't use the same terminology to describe a set of concepts doesn't mean they don't understand those concepts.

Also, I wasn't aware there were were formal qualifications for someone adopting the title of "Programmer", pretty sure big-O notation isn't part of the dictionary definition.

Re: Big-O notation explained by a self-taught programmer

#15

Post by mikebenfield » Sat, Oct 29, 2016, 4:26 PM UTC

bogomipz wrote: post #12

user5994461 wrote: post #11

Earlier quoted context omitted.

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

> "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... Als…

I think (hope?) that user5994461's post was tongue in cheek.

BTW, you are way off saying Don Knuth introduced Big O. It was invented by physicists and mathematicians like Paul Bachmann and Landau, many decades before the 1970s.

Re: Big-O notation explained by a self-taught programmer

#16

Post by hellofunk » Sat, Oct 29, 2016, 4:30 PM UTC

bogomipz wrote: post #12

user5994461 wrote: post #11

Earlier quoted context omitted.

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

> "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... Als…

The thing is that an O(n) algorithm can perform faster than an O(1) algorithm simply because Big-O is only comparing different scenarios on a single routine and not how it compares to other algorithms. A slow algorithm might technically be O(1) but that doesn't necessarily make it fast.

Re: Big-O notation explained by a self-taught programmer

#17

Post by hellofunk » Sat, Oct 29, 2016, 4:33 PM UTC

mrcactu5 wrote: post #7

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

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.

Re: Big-O notation explained by a self-taught programmer

#18

Post by bogomipz » Sat, Oct 29, 2016, 4:33 PM UTC

R_haterade wrote: post #8

mrcactu5 wrote: post #7

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

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…

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.

Re: Big-O notation explained by a self-taught programmer

#19

Post by eweise » Sat, Oct 29, 2016, 4:39 PM UTC

erikbye wrote: post #9

allan_s wrote: post #5

Earlier quoted context omitted.

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 certa…

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…

I've been programming for 25 years and never had a class covering big O notation.

Re: Big-O notation explained by a self-taught programmer

#20

Post by mikebenfield » Sat, Oct 29, 2016, 4:43 PM UTC

erikbye wrote: post #9

allan_s wrote: post #5

Earlier quoted context omitted.

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 certa…

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…

Thank you. As someone who is tangentially connected to software (I'm a mathematician who sometimes intersects with CS/software), the anti-intellectual attitude of some software people is really baffling.

You're working in a field that requires you to use your brain, learn new stuff regularly, and solve problems. Isn't being ignorant of the fundamental concepts of your field a massive red flag that something is wrong?