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

1–10 of 80 posts

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

#3

Post by ambiate »

I find Big-O is mostly applicable to SQL queries. A hard drive/memory bottleneck exists in all database queries. Programmers will easily ignore bad SQL and chalk it up to 'database bottleneck etc'. The truth usually goes along the lines of 'I do not understand temporary tables or views. I just SELECT. I opened a 30,000 row cursor, then, a 1,000,000 row cursor, and finally another 500,000 row cursor and got the data (while storing all of the fetches in leaking arrays)!' Usually on keys without indices or tables without primary keys.

SELECT a, b, c FROM abc (30,000 rows)

BEGIN

  SELECT e, d, f FROM edf WHERE e = a (30k * 1m)

  BEGIN

    SELECT x, y, z FROM xyz WHERE d = x (30k*1m*500k scanned)

    BEGIN

      process()

    END

  END
END

A customer or manager can all find respect in lowering the growth rate of a query. No mathematics required. Simply, "Your report now runs in 30 seconds instead of 20 minutes." Anyone can compute that!

The mathematics of Big-O gets annoying for average case scenarios. Instances of

def fun(abc):

  l=[]

  for x in abc:

    if x%2==0:

      for y in abc:

        l.append(y)

  return l

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

#5

Post by shoyer »

This is a nice explanation, but I couldn't help but notice that the estimate of the number of gumballs in the pictured machine seems closer to 1000 than 100 (contrary to the claim in the article).

You can actually see about 100 gumballs in the picture, so there must be far more hidden behind them -- my guess is closer to 500, which is about twice as close (in order-of-magnitude) to 1000 as to 100.

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

#6

Post by sillysaurus »

This sort of contributes to giving self-taught programmers a rather bad name. The writeup is good, but the idea that Big O is "scary" is just absurd. It's an elementary concept that every working programmer should be familiar with, regardless of whether they're self-taught. Algorithms are not "scary". If you can't reason about algorithms, you may not be a very good programmer yet.

To be clear, I really appreciate the writeup. I just wish it had been framed better. It should be clear that this is for beginner programmers, regardless of whether they have a degree or whether they're self-taught.

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

#7

Post by bps4484 »

This is definitely a good starting point. If you wanted to expand this, I would recommend diving into how the relationship between the real time an algorithm takes to execute and the order of the function, and constants or lesser order terms are unimportant with order notation (can best be shown with graphs, which has already been introduced).

One thing I would stay away from is the talk about "orders of magnitude" because the order of a function and an order of magnitude are very different topics, and it could cause a reader to make bad conclusions like "one algorithm takes 10 seconds to run, one take 100 to run, they must have different big-O notation". I understand why the analogy is made, it's because you're estimating things from a high level, but I think it could cause confusion on the fundamentals.

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

#8

Post by cliveowen »

I don't know first thing about math, but even I find that the classical definition (i.e. that find in the CLRS book) is pretty straightforward: given an input big enough, the running time will be at most that of a multiple of function g(n) if f(n) = O(g(n)), where f is the function that describes the algorithm's running time.

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

#9

Post by tbrownaw »

O(N) is read "Order of N" because the O function is also known as the Order function. I think this is because we're doing approximation, which deals in "orders of magnitude".

It's a different meaning of "order", that has to do with the shape of the size-vs-time curve. It's the same meaning as the order of a polynomial ("x" is linear or 1st order, "x^2" is quadratic or 2nd order, etc).

but Big-O is all about the approximate worst-case performance of doing something.

It can be, but I think it's more commonly taken to mean the average case. One example is quicksort, which is O(n*log(n)) on average but can be quadratic (n^2) in the worst case.

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

#10

Post by yid »

Unfortunately, there are some misconceptions that are propagated in this article. Kudos on the effort, but some statements are just flat out wrong, such as this statement: "Big-O is all about the approximate worst-case performance". Big-O has nothing to do with worst-case, but is a bounding function. An O(n) algorithm is also O(n^2), O(2^n), etc. Those are valid bounds on the O(n) algorithm, just not the smallest.
Post reply on HN