4 ms·

I had an interview the other day and they asked a question on Big O notation to which I didn't really know the answer so guessed it. In 10 years of web dev, bac

by jwmoz 4y ago

I had an interview the other day and they asked a question on Big O notation to which I didn't really know the answer so guessed it. In 10 years of web dev, backend engineering work I've never needed to use it.

LadyCailin 4y ago
You have, you just don’t call it that. You probably know that accessing an array list is faster than a linked list, and a binary tree search is faster than an array list search. What you may not remember is the specific big O notation for those, but that’s not the important thing anyways. The important thing is being able to reason over relative complexities of various operations. When I interview people, I ask the question, but don’t penalize them for not knowing. I penalize them for not being able to re-derive them after reasoning through the algorithm.
- dev_0 4y ago
  After working for years, you will have gut feeling on whether an implementation is slow or fast. This is done with testing on large N dataset
- kasey_junk 4y ago
  Except on modern architectures your intuition about what is actually faster is likely wrong if it’s based on just Big O operation counts. Memory locality, prefetching and branch prediction are all likely more important to actual performance than Big O complexity and those things can change from architecture to architecture. When I was learning big o notation numa architectures where just becoming commercially viable. You’d get dramatically different performance results in one lab to the other based on which machines were in it.
  - LadyCailin 4y ago
    Maybe, but for a given machine, a O(n) algorithm will certainly be worse than O(log n), for non-trivial sizes of n. For trivial sizes, those other things will definitely dominate, and are also good to keep in mind.
- asdev 4y ago
  unless you're working with large datasets, big O hardly matters for most products/business logic
  - LadyCailin 4y ago
    n^2 or worse is so easy to accomplish with embedded for loops. And adding indexes to a DB is a fairly common thing to do with even medium sized DBs. But I do work for a very large company (not FAANG, but close) and so admittedly, the scale there is far larger than in most jobs, and knowing this stuff really does matter a lot more.

by jwmoz 4y ago

LadyCailin 4y ago

You have, you just don’t call it that. You probably know that accessing an array list is faster than a linked list, and a binary tree search is faster than an array list search. What you may not remember is the specific big O notation for those, but that’s not the important thing anyways. The important thing is being able to reason over relative complexities of various operations. When I interview people, I ask the question, but don’t penalize them for not knowing. I penalize them for not being able to re-derive them after reasoning through the algorithm.

dev_0 4y ago
After working for years, you will have gut feeling on whether an implementation is slow or fast. This is done with testing on large N dataset
kasey_junk 4y ago
Except on modern architectures your intuition about what is actually faster is likely wrong if it’s based on just Big O operation counts. Memory locality, prefetching and branch prediction are all likely more important to actual performance than Big O complexity and those things can change from architecture to architecture. When I was learning big o notation numa architectures where just becoming commercially viable. You’d get dramatically different performance results in one lab to the other based on which machines were in it.
- LadyCailin 4y ago
  Maybe, but for a given machine, a O(n) algorithm will certainly be worse than O(log n), for non-trivial sizes of n. For trivial sizes, those other things will definitely dominate, and are also good to keep in mind.
asdev 4y ago
unless you're working with large datasets, big O hardly matters for most products/business logic
- LadyCailin 4y ago
  n^2 or worse is so easy to accomplish with embedded for loops. And adding indexes to a DB is a fairly common thing to do with even medium sized DBs. But I do work for a very large company (not FAANG, but close) and so admittedly, the scale there is far larger than in most jobs, and knowing this stuff really does matter a lot more.