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

Big O Notation – Explained as easily as possible

thatcomputerscientist.com

Post reply on HN
Print view View original

121–130 of 168 posts

Re: Big O Notation – Explained as easily as possible

#121

Post by leonidasv »

kristopolous wrote: post #117
bjeds wrote: post #7

If you are the kind of person that want to read an article titled "explained as easily as possible", I think you should just avoid saying the phrase "big oh" but instead talk about algorithm runtime more informally, like "quicksort has a worst case quadratic but average case n log n runtime". The risk is otherwise you will shoot yourself in the foot, maybe during an interview or other situation, as Big O is just one…

Last summer I was interviewing at a FAANG company for a supposed senior level position and I pointed this out. Instead I was treated as if I fundamentally had no understanding of algorithms whatsoever. It was enormously frustrating, especially when I demonstrated real world runtime to the interviewer of two implementations. If they need someone to actually make things work well on real physical hardware, they need to…

Big O is not about actual hardware, not it should be.

We can argue about it being useful or not, but that don't change this fact.

Re: Big O Notation – Explained as easily as possible

#122

Post by casion »

andi999 wrote: post #27
casion wrote: post #18

Earlier quoted context omitted.

You say it isn't hard, but I have 2 graduate degrees and didn't understand your explanation at all. "Hard" is relative to prerequisite knowledge, which can vary significantly.

Had such students as well. If I ask anything they said, oh I learned that as undergrad (implying that it is too long ago to remember). I am sad about such a waste.

Not sure what this is supposed to mean. Apparently this requires calc knowledge, which I was never required to take!

Re: Big O Notation – Explained as easily as possible

#124

Post by rramadass »

codesparkle wrote: post #115

A bad programmer solves their problems inefficiently and a really bad programmer doesn't even know why their solution is inefficient To any beginners reading this: Solving problems inefficiently does not make you a bad programmer. Most of the time, an "inefficient" solution will be good enough, and optimising for performance comes at a cost. So sit back, relax, and enjoy the journey.

Good caveat; beginners should not bother about any of this stuff. Focus on good modularity, clear code structure and language idioms and in general for readability.

Re: Big O Notation – Explained as easily as possible

#125

Post by kristopolous »

leonidasv wrote: post #121
kristopolous wrote: post #117

Earlier quoted context omitted.

Last summer I was interviewing at a FAANG company for a supposed senior level position and I pointed this out. Instead I was treated as if I fundamentally had no understanding of algorithms whatsoever. It was enormously frustrating, especially when I demonstrated real world runtime to the interviewer of two implementations. If they need someone to actually make things work well on real physical hardware, they need to…

Big O is not about actual hardware, not it should be. We can argue about it being useful or not, but that don't change this fact.

Of course it isn't. Of course it's a mathematical abstraction.

This project required high performance, high throughout, distributed computing with exabytes of data.

The person applying for the job should illustrate they can deal with that and knows when to ask what kind of question.

If they think chalkboard algo analysis is the end of the game, that they can just pack up and go home, not looking at the actual hardware specifications and capabilities, the real world implementations and costs, and just blindly trust the mathematical abstraction without any type of evidence, analysis, testing, or considerations of a system as complex as the physical hardware they are using, then good luck.

For example, if there is a "slower" implementation that's embarrassingly parallelizable and trivial to distribute, those are actually important factors.

If they have a "slower" implementation that also allows for a quicker mark and sweep or cache invalidation, those are also actually important.

If input data can be tightly characterized, that's actually important, it changes the real world expected results.

Bursty and continuous traffic are different problems so average throughput is insufficient for characterization.

This guy disputed all that. Basically the midterm I took 20 years ago as an undergrad when I 18 at the University, that's it. That's all of HPC.

By the end I was just giving him the college freshman level answers and he was genuinely surprised as if he thought I didn't know it.

Again, last I heard, the project is still on the rocks.

Re: Big O Notation – Explained as easily as possible

#126

Post by rramadass »

kodah wrote: post #105

I learned to code as a kid and only met mathematicians who consider themselves programmers as an adult. Some opinion, maybe unpopular: Big O notation can be quite informally understood by normal people. It is academic people that make it and keep it challenging because it is how they understand the world. This is why interviews have stayed materially gruesome despite loud voices wishing it weren't so. It's the langua…

>Big O notation can be quite informally understood by normal people.

Right; the concept is easily understood. It is the rigor of deriving and proving that is made difficult by the mathematicians which need not be that way.

As an example, Here is a neat communication from Faraday to Maxwell on receiving one of Maxwell's paper;

“Maxwell sent this paper to Faraday, who replied: "I was at first almost frightened when I saw so much mathematical force made to bear upon the subject, and then wondered to see that the subject stood it so well." Faraday to Maxwell, March 25, 1857. Campbell, Life, p. 200.

In a later letter, Faraday elaborated:

I hang on to your words because they are to me weighty.... There is one thing I would be glad to ask you. When a mathematician engaged in investigating physical actions and results has arrived at his conclusions, may they not be expressed in common language as fully, clearly, and definitely as in mathematical formulae? If so, would it not be a great boon to such as I to express them so? translating them out of their hieroglyphics ... I have always found that you could convey to me a perfectly clear idea of your conclusions ... neither above nor below the truth, and so clear in character that I can think and work from them. [Faraday to Maxwell, November 13, 1857. Life, p. 206]”

Re: Big O Notation – Explained as easily as possible

#128

Post by proverbialbunny »

bjeds wrote: post #7

If you are the kind of person that want to read an article titled "explained as easily as possible", I think you should just avoid saying the phrase "big oh" but instead talk about algorithm runtime more informally, like "quicksort has a worst case quadratic but average case n log n runtime". The risk is otherwise you will shoot yourself in the foot, maybe during an interview or other situation, as Big O is just one…

>The risk is otherwise you will shoot yourself in the foot, maybe during an interview or other situation

If the point is to identify the speed (or ram consumption) of algorithm, then why not check for that itself instead of the vocabulary in an interview? Why be pedantic when you can instead measure how well they would do as a developer? In an interview you can ask followup questions to see how precise their ability to explain their thought process is.

If someone is so pedantic that they would consider the interviewee to have shot themselves in the foot because they said "The big O is n squared." without any followup questions from the interviewer, that doesn't sound healthy to me. I would worry this kind of culture would extend past the interview and it wouldn't be an enjoyable place to work.

Can you imagine working in a place where people regularly argue over terminology instead of just making sure everyone is on the same page?

(Full warning: I'm not a dev, so I'm coming in from the view of another industry.)

Re: Big O Notation – Explained as easily as possible

#129

Post by thaumasiotes »

Al-Khwarizmi wrote: post #96
bjeds wrote: post #7

If you are the kind of person that want to read an article titled "explained as easily as possible", I think you should just avoid saying the phrase "big oh" but instead talk about algorithm runtime more informally, like "quicksort has a worst case quadratic but average case n log n runtime". The risk is otherwise you will shoot yourself in the foot, maybe during an interview or other situation, as Big O is just one…

I know the rest of the notations in the family but, to be honest, even in most algorithmics textbooks they tend to use Big O like 90% of the time, even in contexts where Big Theta would be more precise (e.g. "mergesort is O(n log n) in all cases"). Let alone in more informal contexts. I don't especially like it, but it's OK because it's not a lie. And I do think for people who just want the gist of the concept, like…

> What irks me is people who use the equal sign as in T(n)=O(n log n), though. Why would a function equal a class? Set membership notation does the job just fine.

It's strange but it's fully standard. I would guess it develops from the use in analysis, where o(n) is more common. You derive your formula, it has a term in it that you don't want, you observe that "complicated term's numerator = o(n)", you take your limit, and the term vanishes away. Use of the = sign makes more sense there, because conceptually you're claiming something about the value of the term. (Specifically, that in the limit, it's equal to zero.)

Re: Big O Notation – Explained as easily as possible

#130

Post by dfdz »

Disclaimer: I am very familiar with big O notation and find it intuitive.

However, I think the notation \lesssim or f(n) \lesssim g(n)

if there is an absolute constant C such that

f(n) \le C g(n)

the meaning is completely clear and by rearranging an expression it can replace big O notation. For example instead of writing

f(n) = g(n) + O(h(n))

you write

|f(n) - g(n)| \lesssim h(n)

https://math.stackexchange.com/questions/1793395/who-introdu...

Post reply on HN