12 ms·

Big O Notation – Using not-boring math to measure code’s efficiency

178 points by rspivak 7y ago

smudgymcscmudge 7y ago
I have a question for those with a better understanding of such things. Is it difficult to calculate time or memory complexity of a function through static analysis? It seems kind of basic, but I still find myself manually checking code instead of relying on a tool.
- zuza 7y ago
  I would argue it isn't tractable. f(n) = f(n-1) + f(n-1) has runtime O(2^n); f(n) = f(n-1) + f(n-2) has runtmie O(~1.62^n); f(n) = f(n/2) + f(n/2) has O(n log n); for i = 1 to f(n) has runtime f(n).. good luck determining a function output through static analysis
  - gizmo686 7y ago
    In both cases it has O(2^n). Normally speaking, this response would be pure pedantry [0], but for static analysis it might be good enough. In most cases, the naive answer will be good enough, and the tool can direct you to pay attention to areas of particular concern. Getting static guarantees about performance would require carefully constructing your code with the tool in mind. [0] Although I still find it outrageous that CS departments describe their algorithms class as "math" when they do not accept this answer.
    - SamReidHughes 7y ago
      They’re asking for the tightest upper bound.
  - enedil 7y ago
    There's master theorem though...
- RodgerTheGreat 7y ago
  For a completely arbitrary program, it is not possible to calculate a tight bound on the time or memory complexity of that that program via static analysis. See Rice's Theorem[0]. It is possible to determine interesting properties of programs if you weaken your requirements to approximations and/or add significant constraints. You can maintain properties by construction if you only allow yourself to use certain kinds of building blocks in assembling programs. The less powerful your computational model, the easier it is to prove things about it. The core idea of a type system is to form a symbolic representation of the semantics of your program which is simpler than the program itself, so that you can prove properties of that simpler system instead of the intractable problem of doing so for the actual program. (If you aren't careful, your type system could end up sufficiently powerful that it is itself undecidable, and you're back where you started.) [0] https://en.wikipedia.org/wiki/Rice's_theorem https://en.wikipedia.org/wiki/Rice's_theorem
  - User23 7y ago
    > For a completely arbitrary program, it is not possible to calculate a tight bound on the time or memory complexity of that that program via static analysis. See Rice's Theorem[0]. That theorem proves that no general algorithm exists. That doesn’t mean it can’t be done for a particular program. The real challenge is that modern compilers and processors will execute in a way that is hard to predict from source code.
    - edejong 7y ago
      The question was whether it is hard to determine the space/time complexity of ‘a’ function, which firmly placed the question in Rice’s theorem grounds.
- kevinventullo 7y ago
  The resolution of the Halting Problem shows you can't even determine whether the complexity is finite!
- pitaj 7y ago
  Given a sufficiently restricted syntax, any static analysis is possible. So the question isn't especially useful with the current wording.
- SamReidHughes 7y ago
  Yes and no - if the function operates on a balanced tree, you might need some way of encoding the constraints the tree follows, and even just describing what “n” is. But if you’re doing merge sort, the function may take n as an integer, and recurse with n/2 and n-n/2, and that is tractable. But generally, no.
- Const-me 7y ago
  If you need precision good enough for practical applications, it’s very hard to do. All modern CPUs are pipelined, time they spent on every instruction depends on neighbor instructions + data dependencies between them. All modern CPUs have multi-level caches, static analyzers must also simulate what data is in which levels of caches; for many practical problems RAM access dominates computations and L1 cache is ~2 orders of magnitude faster than main RAM. All modern CPUs have very sophisticated power management, they scale frequency based on temperature, they selectively turn on/off their blocks, this too affects time. All modern CPUs have multiple cores, L3 cache is often shared across them, all caches suffer heavy penalty when a line is shared across cores. And so on. People don’t do it not only because it’s hard, also because running the function and measuring time + memory is much easier, also much more precise. Even if you don’t care about time and memory complexity and only care about these useless O(N), it’s still very hard because complexity depends on input data. E.g. bubble sort is O(N^2) but it can also be O(N) if the data is mostly sorted already and only a single element needs to be moved.
- adrianN 7y ago
  Yes it's difficult, but people try anyway. The term to Google for is WCET analysis: https://en.wikipedia.org/wiki/Worst-case_execution_time#Automated_approaches https://en.wikipedia.org/wiki/Worst-case_execution_time#Auto...
blattimwind 7y ago
Except Big O Notation is exactly not measuring code's efficiency.
- adrianN 7y ago
  That depends on your definition of efficiency.
  - deleted 7y ago
    [deleted]
  - deleted 7y ago
    [deleted]
MichaelBurge 7y ago
def print_first_item(items): print items[0] This function runs in O(1) time (or "constant time") relative to its input. If this were C where the only types are fixed-size, that might be true. But in Python it seems like items[0] could display as 10 gigabytes of JSON. And if stdout is piped to a process that isn't consuming its input, it might never terminate naturally. Also, since Python has arbitrarily large integers, an expression like "index += 1" probably runs in O(log(index)) time, not O(1) time.
- dpzmick 7y ago
  in C, it items[0] could segfault, the fault could be caught by a signal handler which does some unbounded amount of work, then populates the appropriate memory location and returns... More realistically, the page of memory that items[0] is sitting on could be swapped to disk, requiring the OS to do some big operation. trying to write a piece of code with the big-O you are looking for generally has a huge number of caveats. I'm undecided on whether this is a feature (abstraction) or a flaw (easily misleading)
  - xthestreams 7y ago
    I think you (and others) are misunderstanding the purpose of the big-O notation. It is used to discuss about algorithms, not about their implementation.
  - GuB-42 7y ago
    And "print items[0]" is actually O(n) where n is the size of the string. Maybe even O(n^2) if the item is a big number and a binary to decimal conversion is required. But it is doesn't matter here because we have chosen n to be the size of the array, because it is what we are studying. Here it is big-O "constant time" because the execution time doesn't depend on on the size of the array, assuming it is really big. Not that every call of the function will take the same time to run. The reality is much more complicated, with things like caches to take into account. As a result, complexities under O(n) often don't mean much in practice. But the higher you go, the more important it becomes. As you get to O(n^2) it is time to take a hard look at your algorithms, or make really sure that n is small and stays small.
curiousgal 7y ago
> not-boring math What's next? Gradient decent with no gradients? Fourrier transform with no functions? If math is do boring just skip the whole thing, don't try to kid yourself by saying you're not doing it when you are in fact doing it. /rant
- jrumbut 7y ago
  I was really hoping that this was going to be some lively new way of thinking about or teaching big O notation, "Eulerian path runtime grows like the velocity of a car that drove off a cliff but Hamiltonian path runtime grows like the number of plague bacteria in a petry dish." I was disappointed.
- thiht 7y ago
  What's with this gatekeeping attitude? Big-O notation is a useful tool in a programmer's belt, knowing the math behind it in details is less useful. What's the problem? It's the same thing as not needing to know how an engine works to be able to use a car
  - curiousgal 7y ago
    That is not my point. Big-O notation is a mathematical notation. By using it, you are using math. It's the same as using a car and saying you are not using a car.
    - Toboe 7y ago
      The post isn‘t saying that Big-O isn't math, it is saying Big-O is "not-boring"(->interesting/exciting/whatever) math.
  - mannykannot 7y ago
    That analogy does not really work. To use a modern car for transport, its power source can usually be treated as a black box, but if you don't know the math of Big-O, you don't understand it, and if you don't understand it, you may be unable to apply it in a situation where you have not rote-learned the answer, or, worse, misapply it without noticing. I have seen enough of this to know that it is a real problem.
ajmarcic 7y ago
This article misses an actual definition of Big O. This forces us to skip crucial points like why O(n^2) truly identically equals O(n^2/2 + 5n). The author instead seems to think they are approximately the same because the lower order terms are small compared to the highest one. We only need to explain the definition and the reader could understand why an O(n) algorithm is in O(n^2), why some O(n^3) algorithms are much faster than others in O(n^~2.4), etc.
- devnulloverflow 7y ago
  > The author instead seems to think they are approximately the same because the lower order terms are small compared to the highest one. In fairness, this is actually why we care in practice about asymptotic issues. The fact that there is a rigorous mathematical viewpoint that makes them strictly comparable is helpful for being confident about the non-trivial results -- but the reason we care about it is because we want to know roughly how expensive our code is (or will be).
abalone 7y ago
I've noticed there are SO many of these "coding interview prep" courses lately. Like, obviously it's a hot job market, but there's just so many and of a certain vibe that it seems like some are selling a dream. There's a common narrative too, that it's all about algorithm question prep and it's a "game" you can win. One youtuber who recently landed a ~$275K TC gig said it's not about being "intelligent" it's about practice and rapid pattern recognition (he also was pitching his own coding interview prep course). Said he forgot half of it after getting the job. This could all be true but this narrative is coming from sources that have a financial interest in making you believe that. What do you think HN? I mean I know algorithm prep is an important part of the interview but.. there's just something sketch about all these outfits I can't quite put my finger on. (I also wonder if the people who get hired based on prep vs. aptitude then have a kind of survivor bias and hire others who are strong on this limited range of pattern recognition... could it be a problem for the industry?)
- dgzl 7y ago
  I love your insight, but I don't know much about these courses. Even though I am myself prepping for an interview, I'm just reading CtCi and building the structures and algorithms myself.
- save_ferris 7y ago
  A major force driving this is the employers who choose to conduct interviews in this way. I'm a developer with about 6 years experience in full stack web app development (Rails & Django mostly), and I recently got my ass absolutely kicked during a couple of live coding challenges that were very heavy on theory (also worth mentioning that I'm a self-taught dev without a CS degree). I started talking to some former coworkers about my experience, and I got 2 main responses: A) it's imperative to have a CS foundation regardless of your degree if you want to advance in your career, and B) employers only consider prior experience to certain degree. The two interviews that I bombed involved heavily contrived coding challenges that tested CS fundamentals in ways that I've never encountered in a professional environment, so it doesn't surprise me at all to see services like this popping up.
  - 7y ago
raxxorrax 7y ago
> Big O notation is [...] about how long an algorithm takes to run. My former prof would have me spanked for an imprecise statement like this.
Blackthorn 7y ago
You're an engineer, aren't you? Just do the damn "boring" math.
iandanforth 7y ago
Question: At what point in a career do you expect someone to have gone from "I know Big O" to "I know how this data structure is laid out in memory on this OS?" My experience says really good engineers know the latter, but I'd like to hear if this holds for others.
- bauerd 7y ago
  How data structures are laid out in memory has nothing to do with the operating system
  - blattimwind 7y ago
    OS typically dictates ABI, ABI dictates memory layout of structures, among other things.
trax 7y ago
I like that math is a gate that you need to pass to prove yourself. The fact that you're a code monkey can get you so far. You need to know the fundamentals and be able to think. HN hates math. Good, less competition.
gameguy43 7y ago
Original author here. Thanks for the post! Would stick around to answer questions but I'm on vacation in Japan right now! We're doing a poor job with navigation on the site ATM, so here are some "you might also like" hits for you: A piece where we derive most of the main data structures step by step, starting with naked bits in RAM: - https://www.interviewcake.com/data-structures-and-algorithms-guide https://www.interviewcake.com/data-structures-and-algorithms... A reference / cheat sheet for the main data structures: - https://www.interviewcake.com/data-structures-reference https://www.interviewcake.com/data-structures-reference A reference / cheat sheet for sorting algorithms: - https://www.interviewcake.com/sorting-algorithm-cheat-sheet https://www.interviewcake.com/sorting-algorithm-cheat-sheet
falcor84 7y ago
> As n gets really big, adding 100 or dividing by 2 has a decreasingly significant effect. I was annoyed to see that comment about division, as of course dividing n by 2 has exactly the same effect regardless of the size of n. This is not the reason we ignore multiplicative constants in complexity analysis. It reminded me of the joke that Earth's circumference is pretty much the same as its diameter, since the the size of pi is negligible at that scale.
- concert-gilled 7y ago
  > This is not the reason we ignore multiplicative constants in complexity analysis. What is the reason?
  - Jaxan 7y ago
    One possible answer is that any algorithm can be sped up linearly: https://en.m.wikipedia.org/wiki/Linear_speedup_theorem https://en.m.wikipedia.org/wiki/Linear_speedup_theorem . (At least theoretically, for runtimes bigger than linear.) Another answer could be Moore's law: machines do get faster over time. (And also memory gets cheaper.) And so we wish to define efficiency (time or space) in a way which does not depend on the current technological state.
    - dooglius 7y ago
      That theorem just indicates that Turing Machines with an unbounded/arbitrary number of symbols is a poor model; the approach there will not work on any actual machine. If you take out a factor of 2 in an algorithm, that's going to asymptotically double the state regardless of what actual machine you're on, so I don't buy machine-independence as a reasonable excuse. The actual reason constants are ignored is because it makes the math a lot simpler when you ignore them.
  - rand_r 7y ago
    One part is that Big-O is an upper bound that kicks in for sufficiently large n. For example, a O(log(n)) function will be faster than a O(k * n) function, for any fixed k, when n>j (for some fixed j i.e. when n is large enough). When comparing major classes of functions (n, log(n), 2^n, etc,), constant multiples don't matter, mathematically. The other reason is that when comparing two functions with a similar amount of constant steps, let's say 5n vs 2n, it's impossible to say which is faster in the real world, so it's simpler and just as useful to collapse the set of O(k * f(n)) functions into O(f(n)).
kgilpin 7y ago
It's true that most engineers are not going to implement a binary search algorithm or an optimizing compiler during the course of their employment in a typical year. However, CS fundamentals are the language of software engineering. It's important for engineers to be able to communicate efficiently about things like runtime analysis, indexes, concurrency models, type systems, etc. Your mechanic knows how a carburetor works, (s)he knows how brakes work. Mechanics have a common set of fundamentals that they all know and share, and can use to communicate with each other about their work. The purpose of this knowledge is not to be able to fabricate new car parts, although given time and the right equipment, it could probably be done. The purpose of CS fundamentals is not to so much to implement complex algorithms, as to understand how to use tools and libraries that are based on them.
sireat 7y ago
Am I the only one who signed up for interviewcake on a whim (similar to those January fitness club resolutions)? Then I sort of had an epiphany. When will I need this? (or rather "I am too old for this...") I must be the perfect customer for interview cake: paid but do not use it. I make my own work and those kind of problems just do not come up. I mean CLRS was fun a long time ago, but it seems to degenerate into skeet shooting pretty quickly: “Shooting skeet eight hours a month was excellent training for them. It trained them to shoot skeet.”

178 points by rspivak 7y ago

I have a question for those with a better understanding of such things. Is it difficult to calculate time or memory complexity of a function through static analysis? It seems kind of basic, but I still find myself manually checking code instead of relying on a tool.

zuza 7y ago
I would argue it isn't tractable. f(n) = f(n-1) + f(n-1) has runtime O(2^n); f(n) = f(n-1) + f(n-2) has runtmie O(~1.62^n); f(n) = f(n/2) + f(n/2) has O(n log n); for i = 1 to f(n) has runtime f(n).. good luck determining a function output through static analysis
- gizmo686 7y ago
  In both cases it has O(2^n). Normally speaking, this response would be pure pedantry [0], but for static analysis it might be good enough. In most cases, the naive answer will be good enough, and the tool can direct you to pay attention to areas of particular concern. Getting static guarantees about performance would require carefully constructing your code with the tool in mind. [0] Although I still find it outrageous that CS departments describe their algorithms class as "math" when they do not accept this answer.
  - SamReidHughes 7y ago
    They’re asking for the tightest upper bound.
- enedil 7y ago
  There's master theorem though...
RodgerTheGreat 7y ago
For a completely arbitrary program, it is not possible to calculate a tight bound on the time or memory complexity of that that program via static analysis. See Rice's Theorem[0]. It is possible to determine interesting properties of programs if you weaken your requirements to approximations and/or add significant constraints. You can maintain properties by construction if you only allow yourself to use certain kinds of building blocks in assembling programs. The less powerful your computational model, the easier it is to prove things about it. The core idea of a type system is to form a symbolic representation of the semantics of your program which is simpler than the program itself, so that you can prove properties of that simpler system instead of the intractable problem of doing so for the actual program. (If you aren't careful, your type system could end up sufficiently powerful that it is itself undecidable, and you're back where you started.) [0] https://en.wikipedia.org/wiki/Rice's_theorem https://en.wikipedia.org/wiki/Rice's_theorem
- User23 7y ago
  > For a completely arbitrary program, it is not possible to calculate a tight bound on the time or memory complexity of that that program via static analysis. See Rice's Theorem[0]. That theorem proves that no general algorithm exists. That doesn’t mean it can’t be done for a particular program. The real challenge is that modern compilers and processors will execute in a way that is hard to predict from source code.
  - edejong 7y ago
    The question was whether it is hard to determine the space/time complexity of ‘a’ function, which firmly placed the question in Rice’s theorem grounds.
kevinventullo 7y ago
The resolution of the Halting Problem shows you can't even determine whether the complexity is finite!
pitaj 7y ago
Given a sufficiently restricted syntax, any static analysis is possible. So the question isn't especially useful with the current wording.
SamReidHughes 7y ago
Yes and no - if the function operates on a balanced tree, you might need some way of encoding the constraints the tree follows, and even just describing what “n” is. But if you’re doing merge sort, the function may take n as an integer, and recurse with n/2 and n-n/2, and that is tractable. But generally, no.
Const-me 7y ago
If you need precision good enough for practical applications, it’s very hard to do. All modern CPUs are pipelined, time they spent on every instruction depends on neighbor instructions + data dependencies between them. All modern CPUs have multi-level caches, static analyzers must also simulate what data is in which levels of caches; for many practical problems RAM access dominates computations and L1 cache is ~2 orders of magnitude faster than main RAM. All modern CPUs have very sophisticated power management, they scale frequency based on temperature, they selectively turn on/off their blocks, this too affects time. All modern CPUs have multiple cores, L3 cache is often shared across them, all caches suffer heavy penalty when a line is shared across cores. And so on. People don’t do it not only because it’s hard, also because running the function and measuring time + memory is much easier, also much more precise. Even if you don’t care about time and memory complexity and only care about these useless O(N), it’s still very hard because complexity depends on input data. E.g. bubble sort is O(N^2) but it can also be O(N) if the data is mostly sorted already and only a single element needs to be moved.
adrianN 7y ago
Yes it's difficult, but people try anyway. The term to Google for is WCET analysis: https://en.wikipedia.org/wiki/Worst-case_execution_time#Automated_approaches https://en.wikipedia.org/wiki/Worst-case_execution_time#Auto...

blattimwind 7y ago

Except Big O Notation is exactly not measuring code's efficiency.

adrianN 7y ago
That depends on your definition of efficiency.
- deleted 7y ago
  [deleted]
- deleted 7y ago
  [deleted]

MichaelBurge 7y ago

def print_first_item(items): print items[0] This function runs in O(1) time (or "constant time") relative to its input. If this were C where the only types are fixed-size, that might be true. But in Python it seems like items[0] could display as 10 gigabytes of JSON. And if stdout is piped to a process that isn't consuming its input, it might never terminate naturally. Also, since Python has arbitrarily large integers, an expression like "index += 1" probably runs in O(log(index)) time, not O(1) time.

dpzmick 7y ago
in C, it items[0] could segfault, the fault could be caught by a signal handler which does some unbounded amount of work, then populates the appropriate memory location and returns... More realistically, the page of memory that items[0] is sitting on could be swapped to disk, requiring the OS to do some big operation. trying to write a piece of code with the big-O you are looking for generally has a huge number of caveats. I'm undecided on whether this is a feature (abstraction) or a flaw (easily misleading)
- xthestreams 7y ago
  I think you (and others) are misunderstanding the purpose of the big-O notation. It is used to discuss about algorithms, not about their implementation.
- GuB-42 7y ago
  And "print items[0]" is actually O(n) where n is the size of the string. Maybe even O(n^2) if the item is a big number and a binary to decimal conversion is required. But it is doesn't matter here because we have chosen n to be the size of the array, because it is what we are studying. Here it is big-O "constant time" because the execution time doesn't depend on on the size of the array, assuming it is really big. Not that every call of the function will take the same time to run. The reality is much more complicated, with things like caches to take into account. As a result, complexities under O(n) often don't mean much in practice. But the higher you go, the more important it becomes. As you get to O(n^2) it is time to take a hard look at your algorithms, or make really sure that n is small and stays small.

curiousgal 7y ago

> not-boring math What's next? Gradient decent with no gradients? Fourrier transform with no functions? If math is do boring just skip the whole thing, don't try to kid yourself by saying you're not doing it when you are in fact doing it. /rant

jrumbut 7y ago
I was really hoping that this was going to be some lively new way of thinking about or teaching big O notation, "Eulerian path runtime grows like the velocity of a car that drove off a cliff but Hamiltonian path runtime grows like the number of plague bacteria in a petry dish." I was disappointed.
thiht 7y ago
What's with this gatekeeping attitude? Big-O notation is a useful tool in a programmer's belt, knowing the math behind it in details is less useful. What's the problem? It's the same thing as not needing to know how an engine works to be able to use a car
- curiousgal 7y ago
  That is not my point. Big-O notation is a mathematical notation. By using it, you are using math. It's the same as using a car and saying you are not using a car.
  - Toboe 7y ago
    The post isn‘t saying that Big-O isn't math, it is saying Big-O is "not-boring"(->interesting/exciting/whatever) math.
- mannykannot 7y ago
  That analogy does not really work. To use a modern car for transport, its power source can usually be treated as a black box, but if you don't know the math of Big-O, you don't understand it, and if you don't understand it, you may be unable to apply it in a situation where you have not rote-learned the answer, or, worse, misapply it without noticing. I have seen enough of this to know that it is a real problem.

ajmarcic 7y ago

This article misses an actual definition of Big O. This forces us to skip crucial points like why O(n^2) truly identically equals O(n^2/2 + 5n). The author instead seems to think they are approximately the same because the lower order terms are small compared to the highest one. We only need to explain the definition and the reader could understand why an O(n) algorithm is in O(n^2), why some O(n^3) algorithms are much faster than others in O(n^~2.4), etc.

devnulloverflow 7y ago
> The author instead seems to think they are approximately the same because the lower order terms are small compared to the highest one. In fairness, this is actually why we care in practice about asymptotic issues. The fact that there is a rigorous mathematical viewpoint that makes them strictly comparable is helpful for being confident about the non-trivial results -- but the reason we care about it is because we want to know roughly how expensive our code is (or will be).

abalone 7y ago

I've noticed there are SO many of these "coding interview prep" courses lately. Like, obviously it's a hot job market, but there's just so many and of a certain vibe that it seems like some are selling a dream. There's a common narrative too, that it's all about algorithm question prep and it's a "game" you can win. One youtuber who recently landed a ~$275K TC gig said it's not about being "intelligent" it's about practice and rapid pattern recognition (he also was pitching his own coding interview prep course). Said he forgot half of it after getting the job. This could all be true but this narrative is coming from sources that have a financial interest in making you believe that. What do you think HN? I mean I know algorithm prep is an important part of the interview but.. there's just something sketch about all these outfits I can't quite put my finger on. (I also wonder if the people who get hired based on prep vs. aptitude then have a kind of survivor bias and hire others who are strong on this limited range of pattern recognition... could it be a problem for the industry?)

dgzl 7y ago
I love your insight, but I don't know much about these courses. Even though I am myself prepping for an interview, I'm just reading CtCi and building the structures and algorithms myself.
save_ferris 7y ago
A major force driving this is the employers who choose to conduct interviews in this way. I'm a developer with about 6 years experience in full stack web app development (Rails & Django mostly), and I recently got my ass absolutely kicked during a couple of live coding challenges that were very heavy on theory (also worth mentioning that I'm a self-taught dev without a CS degree). I started talking to some former coworkers about my experience, and I got 2 main responses: A) it's imperative to have a CS foundation regardless of your degree if you want to advance in your career, and B) employers only consider prior experience to certain degree. The two interviews that I bombed involved heavily contrived coding challenges that tested CS fundamentals in ways that I've never encountered in a professional environment, so it doesn't surprise me at all to see services like this popping up.
- 7y ago

raxxorrax 7y ago

> Big O notation is [...] about how long an algorithm takes to run. My former prof would have me spanked for an imprecise statement like this.

Blackthorn 7y ago

You're an engineer, aren't you? Just do the damn "boring" math.

iandanforth 7y ago

Question: At what point in a career do you expect someone to have gone from "I know Big O" to "I know how this data structure is laid out in memory on this OS?" My experience says really good engineers know the latter, but I'd like to hear if this holds for others.

bauerd 7y ago
How data structures are laid out in memory has nothing to do with the operating system
- blattimwind 7y ago
  OS typically dictates ABI, ABI dictates memory layout of structures, among other things.

trax 7y ago

I like that math is a gate that you need to pass to prove yourself. The fact that you're a code monkey can get you so far. You need to know the fundamentals and be able to think. HN hates math. Good, less competition.

gameguy43 7y ago

Original author here. Thanks for the post! Would stick around to answer questions but I'm on vacation in Japan right now! We're doing a poor job with navigation on the site ATM, so here are some "you might also like" hits for you: A piece where we derive most of the main data structures step by step, starting with naked bits in RAM: - https://www.interviewcake.com/data-structures-and-algorithms-guide https://www.interviewcake.com/data-structures-and-algorithms... A reference / cheat sheet for the main data structures: - https://www.interviewcake.com/data-structures-reference https://www.interviewcake.com/data-structures-reference A reference / cheat sheet for sorting algorithms: - https://www.interviewcake.com/sorting-algorithm-cheat-sheet https://www.interviewcake.com/sorting-algorithm-cheat-sheet

falcor84 7y ago

> As n gets really big, adding 100 or dividing by 2 has a decreasingly significant effect. I was annoyed to see that comment about division, as of course dividing n by 2 has exactly the same effect regardless of the size of n. This is not the reason we ignore multiplicative constants in complexity analysis. It reminded me of the joke that Earth's circumference is pretty much the same as its diameter, since the the size of pi is negligible at that scale.

concert-gilled 7y ago
> This is not the reason we ignore multiplicative constants in complexity analysis. What is the reason?
- Jaxan 7y ago
  One possible answer is that any algorithm can be sped up linearly: https://en.m.wikipedia.org/wiki/Linear_speedup_theorem https://en.m.wikipedia.org/wiki/Linear_speedup_theorem . (At least theoretically, for runtimes bigger than linear.) Another answer could be Moore's law: machines do get faster over time. (And also memory gets cheaper.) And so we wish to define efficiency (time or space) in a way which does not depend on the current technological state.
  - dooglius 7y ago
    That theorem just indicates that Turing Machines with an unbounded/arbitrary number of symbols is a poor model; the approach there will not work on any actual machine. If you take out a factor of 2 in an algorithm, that's going to asymptotically double the state regardless of what actual machine you're on, so I don't buy machine-independence as a reasonable excuse. The actual reason constants are ignored is because it makes the math a lot simpler when you ignore them.
- rand_r 7y ago
  One part is that Big-O is an upper bound that kicks in for sufficiently large n. For example, a O(log(n)) function will be faster than a O(k * n) function, for any fixed k, when n>j (for some fixed j i.e. when n is large enough). When comparing major classes of functions (n, log(n), 2^n, etc,), constant multiples don't matter, mathematically. The other reason is that when comparing two functions with a similar amount of constant steps, let's say 5n vs 2n, it's impossible to say which is faster in the real world, so it's simpler and just as useful to collapse the set of O(k * f(n)) functions into O(f(n)).

kgilpin 7y ago

It's true that most engineers are not going to implement a binary search algorithm or an optimizing compiler during the course of their employment in a typical year. However, CS fundamentals are the language of software engineering. It's important for engineers to be able to communicate efficiently about things like runtime analysis, indexes, concurrency models, type systems, etc. Your mechanic knows how a carburetor works, (s)he knows how brakes work. Mechanics have a common set of fundamentals that they all know and share, and can use to communicate with each other about their work. The purpose of this knowledge is not to be able to fabricate new car parts, although given time and the right equipment, it could probably be done. The purpose of CS fundamentals is not to so much to implement complex algorithms, as to understand how to use tools and libraries that are based on them.

sireat 7y ago

Am I the only one who signed up for interviewcake on a whim (similar to those January fitness club resolutions)? Then I sort of had an epiphany. When will I need this? (or rather "I am too old for this...") I must be the perfect customer for interview cake: paid but do not use it. I make my own work and those kind of problems just do not come up. I mean CLRS was fun a long time ago, but it seems to degenerate into skeet shooting pretty quickly: “Shooting skeet eight hours a month was excellent training for them. It trained them to shoot skeet.”