Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Big-O notation explained by a self-taught programmer

justin.abrah.ms

Post reply on HN
Print view View original

41–50 of 58 posts

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

#41

Post by RandomOpinion »

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…

Yep, have to agree with this. People who don't know big-O notation (and other CS fundamentals) are the ones gluing together libraries and code built by people who do. Now there's nothing wrong with that; there's enough work to be done for all of us. However, it's not something to crow about either.

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

#42

Post by _greim_ »

BjoernKW wrote: post #35
achr2 wrote: post #21

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

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.

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.

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

#43

Post by bogomipz »

mikebenfield wrote: post #15
bogomipz wrote: post #12

Earlier quoted context omitted.

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

I didn't know the OPs post was tongue and cheek. Sometimes it hard to tell : )

Sure "O" goes back to mathematicians in the late 19th century. What I meant was that Knuth introduced Big O(mnicron) in the context of "Computer Science" literature.

This is the source I am referring to from 1976 SIGACT News:

http://www.phil.uu.nl/datastructuren/09-10/knuth_big_omicron...

On page 21 or page 4 of the PDF:

"I would like to close this letter by discussing a competing way to denote the order of function growth. My library research turned up the surprising fact that this alternative approach actually antedates the O-notation itself. "

On page 22 or page 5 of the PDF:

"The main reason why 0 is so handy is that we can use it right in the middle of formulas (and in the middle of English sentences and in tables which show the running times for a family of related algorithms etc.)."

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

#44

Post by bogomipz »

pluma wrote: post #31
gk101 wrote: post #27

Earlier quoted context omitted.

Yes, however big O notation isn't about which programs run faster, it's about how the runtime of a program changes in response to the input size

...which is irrelevant depending on the bounds of the input size. It boils down to optimization. There's no point in spending time optimizing for Big-O if the input size will be so small the difference between O(n²) and O(n log n) doesn't matter. As with all optimizations, there are situations where it matters a lot. But in the real world there are plenty of situations where the time is better spent elsewhere or wher…

But this fact is accounted for in the definition of Big O in the "for all n > k" no?

"f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. "

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

#45

Post by FreeFull »

_greim_ wrote: post #42
BjoernKW wrote: post #35

Earlier quoted context omitted.

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.

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.

It can also be the case that an algorithm with a worse big-O complexity might actually be better because all your inputs are small and the constant multiplier is lower than the more complicated, better big-O algorithm

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

#46

Post by bogomipz »

castratikron wrote: post #26

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. :)

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.

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

#47

Post by R_haterade »

gk101 wrote: post #22
R_haterade wrote: post #8

Earlier quoted context omitted.

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…

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…

Agreed, but this was for a fast script that will probably run 100 times for analysis purposes--the code itself wasn't the end goal. I just needed something that could crunch my numbers in 10 minutes instead of 2 hours. :-)

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

#48

Post by R_haterade »

bogomipz wrote: post #18
R_haterade wrote: post #8

Earlier quoted context omitted.

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

I will have to check this out as I'm in a lot of places where speed matters these days.

Does he delve into the nuts and bolts of data structure for this, or does it stay more theoretical?

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

#49

Post by R_haterade »

gk101 wrote: post #22
R_haterade wrote: post #8

Earlier quoted context omitted.

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…

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…

I do want to express that I appreciate the effort you put into this post. Algorithms and data structures are my weakest point right now, and being able to read through your explanation is a helpful thing.

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

#50

Post by bogomipz »

R_haterade wrote: post #48
bogomipz wrote: post #18

Earlier quoted context omitted.

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

I will have to check this out as I'm in a lot of places where speed matters these days. Does he delve into the nuts and bolts of data structure for this, or does it stay more theoretical?

Its both. Here are some links:

Video Lectures are here: https://www.coursera.org/learn/analysis-of-algorithms

and the book:

http://aofa.cs.princeton.edu/home/

Also a youtube - short history of algorithm analysis by Sedgewick is worth a watch:

https://www.youtube.com/watch?v=qap2MyBTSZk

Post reply on HN