Hacker News Reader

Comment by lmilcin | Hacker News Reader

What is not applicable?

If one person says a linked list is faster than an array list but the opposite is true, then why do you claim it is not applicable?

Isn't it exactly the point of the article, that sometime you need to say what the interviewer wants to hear rather than what is the actual truth?

It is an unfortunate truth that a lot of interviewers will ask about linked lists vs array lists and at the same time will not understand that linked lists will be slower for insertions or deletions in most cases.

That is because you first need to find the insertion/deletion place, and any benefit of faster insertion/deletion for linked list will be offset by much slower search.

View on HN

None of the comments above yours in the thread mention any form of the word "fast" or "speed". They mention "performance" in reference to big-O complexity. Big-O is not always about speed.

> None of the comments above yours in the thread mention any form of the word "fast" or "speed". They mention "performance" in reference to big-O complexity. Big-O is not always about speed.

I am sorry, do you want to say "performance" and "big-O" have nothing to with trying to make the program go faster?

I think you have lost your way and need to backtrack a little bit.

The whole point of big-O analysis is to be able to reason about how fast a program will be given input size.

No it’s not, it’s about trying to quantify algorithmic complexity.

"Performance" depends on a number of factors beyond the code itself.

To take a real world example, immutable operations in Javascript are often more performant than mutable operations--thanks to the fact that the Chrome Engine "cheats" with its hot path functionality.

However, in Big O, constantly generating new data structures, even within loops, would clearly trash the algorithm's space complexity. On compilers that don't optimize for immutability, the Big O algorithm is more performant; on the ones that do, the immutable approach is more performant.

It's because of example like these that you want to disconnect the concept of "performance" from Big O. Because context matters for the former, while the latter relates only to the algorithm itself.

If I ask for something to be done in O(1) I'm not asking for it to be fast, I'm asking for it to take the exact same amount of time every time no matter what. That might end up being slower, but so what, maybe that's what I need.

If I ask for an O(1) algorithm and you build something that is as fast as possible, faster in every case, but sometimes it's really fast and sometimes it's a little less fast but still fast -- well, then it's not O(1) and not what I asked for. It may be fast, but if it's sometimes faster than at other times it's not O(1).

Thus, I do not consider big-O to be synonymous with speed. They are different, because the best possible big-O, O(1), does not necessarily mean the fastest.

I'm confused - that isn't what I understand O(1) to mean. To me, O(1) means only that there exists some constant that bounds the runtime, while individual invocations can absolutely be sometimes faster.

Well, not exactly.

What it really means is that the execution time does not depend on the size of input (n).

What it does not say is how much time it takes to execute, whether it is exactly same amount of time every time or whether there exists some kind of upper bound on execution time.

For example, an algorithm that takes 1/(randFloat()) time to insert an element to the data structure where randFloat() returns any possible floating point number with equal distribution, is still O(1) algorithm, even though there is no upper limit on how long it can take to execute.

> an algorithm that takes 1/(randFloat()) time to insert an element to the data structure where randFloat() returns any possible floating point number with equal distribution, is still O(1) algorithm, even though there is no upper limit on how long it can take to execute.

According to the definition, if 1/(randFloat()) = O(1) then there must be a constant M that satisfies 1/(randFloat()) <= M * 1. But according to your own words there's no upper limit to 1/(randFloat()), therefore there's no such constant M, therefore it's not O(1).

(In practice on most systems there would be an upper limit since a float can't be infinitely close to zero, but let's act as if that wasn't the case.)

More a case of "f(n) = 1/randFloat() does not have a well-defined limit as n goes to infinity", so it would be hard to say that it fits in ANY complexity class.

What is, however, clear is that its run-time does not depend on the size of the input. And technically, that means we can find a constant (infinity) that always... But, that is pretty unsatisfying.

https://www.quora.com/Why-isnt-infinity-a-constant

A hash table has E[O(1)] inserts and lookups. Most people ignore the expected part and just say those operations are O(1).

Asymptotic complexity is of course only loosely correlated with speed. In real systems with real workload sizes, constant factors matter a lot.

> Thus, I do not consider big-O to be synonymous with speed. They are different, because the best possible big-O, O(1), does not necessarily mean the fastest.

Maybe not synonymous in the sense of technically exactly equal, but certainly a pretty good approximation -- and absolutely synonymous in the sense that the whole purpose of big-O notation is to be able to reason about speed in more general terms, comparing algorithms in pseudo code in stead of having to actually write the program so you can run it through a benchmark.

So, no: If "the best possible big-O, O(1), does not necessarily mean the fastest," then it isn't actually the best.

Replying here because I can't to the relevant comment:

> No it’s not, it’s about trying to quantify algorithmic complexity.

And what would you say is the goal of quantifying algorithmic complexity?

In cryptography the goal might be to ensure the algorithm always takes the exact same amount of time, or the exact same number of CPU instructions, even if it is slower than alternatives. This is a case where we are interested in complexity without regard to speed.

Thus, the answer to why we care about complexity is "it depends". But it is not always about speed.

BTW I've found that in cases where the reply and/or edit button(s) disappear, refreshing the page usually causes them to appear.

There's a delay before the reply button appears to encourage more thought as discussions get deeper. A HN thing.

Wow I thought this was some rendering bug for the longest time. Is there any (un)official list of HN quirks, out of curiosity?

In those cases, if you click on the "X minutes ago" timestamp you'll get a single comment view with a reply box. Yours didn't have a reply link in-thread, so just like I did here.

> The whole point of big-O analysis is to be able to reason about how fast a program will be given input size.

It's an important technicality that matters when you are doing performance tuning of code on modern CPU's. Big-O is asymptotic but omits the constant multiplier, so if you're comparing, for example, deletion from a naive binary search tree vs. an unsorted array, it's not necessarily obvious that a tree search on a naive pointer based tree (O(log n)) is faster than a find, swap, and delete (O(n)) until n is sufficiently large.

Another example is iterating through the pixels of a very large bitmap on the order of 10m+ pixels. While iterating through all pixels should be linear to the number of pixels (O(width * height)), assuming it's a row-oriented bitmap, which most are, scanning row by row can be substantially faster than scanning column by column because of caching behaviors.

Point being, big-O and actual performance are not always the same thing because the constant factor can sometimes dominate depending on what you're trying to do.

Reply on news.ycombinator.com