4 ms·

The author isn't confused, rather that is the point he is making. Often schools teach you to only focus on the big O and ignore the constant multiplier. Those

The author isn't confused, rather that is the point he is making. Often schools teach you to only focus on the big O and ignore the constant multiplier. Those same schools then teach vectors and linked lists as the two main data structures. They talk about the cases where one has an obvious strength over the other, such as inserting into the middle, or using an index to access an element in the middle. However, they tend to skim over scenarios where the big O notation is the same but one has an advantage due to the constant multiplier, leading many students to come away with the impression that big O notation is all that matters.

the_af 4y ago
> Often schools teach you to only focus on the big O and ignore the constant multiplier That's news to me. Which schools teach you that? Where I studied CS, algorithmic complexity and Big-O was taught in Graph Theory (Discrete Maths), and no attempt was made to imply it was about run time in milliseconds. The problem might be that there's plenty of self-taught programmers writing blogs that talk about Big-O without understanding what it means, and people who "learn" about it from said blogs. There's no theoretical mismatch with reality here. The only confusion might lie in the minds of self-taught programmers.
- xpe 4y ago
  Fair points. Still, statistically, it is useful to recognize the empirical (but imperfect) correlation between Big-O and run time. One does not have to be confused to know this. Rather, one would be lacking perspective to not recognize that there is a connection. This connection is important if you want to be empirical validation of an algorithm on a particular computer. I just want to point out that your comment could easily be perceived as a ding against self-taught programmers. Many self-taught programmers (which I will define as ones that have not had a formal CS degree) read extensively. Many use their intrinsic motivation to really dive in. Also, many are successful. Bill Gates is one example. Yes, there are programmers of all kinds that have a tendency to write sloppy blog posts, to make overconfident and inaccurate statements, to forget things they've read, to hack their way around, and so on. There may even be a statistical correlation between self-taught programmers and such behavior. But I'd suggest we points out those behaviors when they are a problem rather than make assumptions about their educational backgrounds.
- xpe 4y ago
  > Where I studied CS, algorithmic complexity and Big-O was taught in Graph Theory (Discrete Maths) I may be misunderstanding you?... In my study and practice of complexity theory, algorithms related to graph theory are an object of analysis of complexity theory, not a conceptual foundation for it.
- xpe 4y ago
  This paragraph is useful because it clears up some potential confusion between how computational complexity theory and algorithmic analysis are used: > Yet another subject related to computational complexity theory is algorithmic analysis (e.g. Knuth (1973), Cormen, Leiserson, and Rivest 2005). Like computational complexity theory, algorithmic analysis studies the complexity of problems and also uses the time and space measures `t_M(n)` and `s_M(x)` defined above. The methodology of algorithmic analysis is different from that of computational complexity theory in that it places primary emphasis on gauging the efficiency of specific algorithms for solving a given problem. On the other hand, in seeking to classify problems according to their degree of intrinsic difficulty, complexity theory must consider the efficiency of all algorithms for solving a problem. Complexity theorists thus make greater use of complexity classes such as P, NP, and PSPACE whose definitions are robust across different choices of reference model. In algorithmic analysis, on the other hand, algorithms are often characterized relative to the finer-grained hierarchy of running times `log_2(n)`, `n`, `n log_2(n)`, `n^2`, `n^3`, ... within P. Source: https://plato.stanford.edu/entries/computational-complexity/ https://plato.stanford.edu/entries/computational-complexity/ Note: I've done some light edits so the mathematics are roughly in LaTeX syntax; e.g. `_` for subscripts.

the_af 4y ago

> Often schools teach you to only focus on the big O and ignore the constant multiplier That's news to me. Which schools teach you that? Where I studied CS, algorithmic complexity and Big-O was taught in Graph Theory (Discrete Maths), and no attempt was made to imply it was about run time in milliseconds. The problem might be that there's plenty of self-taught programmers writing blogs that talk about Big-O without understanding what it means, and people who "learn" about it from said blogs. There's no theoretical mismatch with reality here. The only confusion might lie in the minds of self-taught programmers.

xpe 4y ago
Fair points. Still, statistically, it is useful to recognize the empirical (but imperfect) correlation between Big-O and run time. One does not have to be confused to know this. Rather, one would be lacking perspective to not recognize that there is a connection. This connection is important if you want to be empirical validation of an algorithm on a particular computer. I just want to point out that your comment could easily be perceived as a ding against self-taught programmers. Many self-taught programmers (which I will define as ones that have not had a formal CS degree) read extensively. Many use their intrinsic motivation to really dive in. Also, many are successful. Bill Gates is one example. Yes, there are programmers of all kinds that have a tendency to write sloppy blog posts, to make overconfident and inaccurate statements, to forget things they've read, to hack their way around, and so on. There may even be a statistical correlation between self-taught programmers and such behavior. But I'd suggest we points out those behaviors when they are a problem rather than make assumptions about their educational backgrounds.
xpe 4y ago
> Where I studied CS, algorithmic complexity and Big-O was taught in Graph Theory (Discrete Maths) I may be misunderstanding you?... In my study and practice of complexity theory, algorithms related to graph theory are an object of analysis of complexity theory, not a conceptual foundation for it.
xpe 4y ago
This paragraph is useful because it clears up some potential confusion between how computational complexity theory and algorithmic analysis are used: > Yet another subject related to computational complexity theory is algorithmic analysis (e.g. Knuth (1973), Cormen, Leiserson, and Rivest 2005). Like computational complexity theory, algorithmic analysis studies the complexity of problems and also uses the time and space measures `t_M(n)` and `s_M(x)` defined above. The methodology of algorithmic analysis is different from that of computational complexity theory in that it places primary emphasis on gauging the efficiency of specific algorithms for solving a given problem. On the other hand, in seeking to classify problems according to their degree of intrinsic difficulty, complexity theory must consider the efficiency of all algorithms for solving a problem. Complexity theorists thus make greater use of complexity classes such as P, NP, and PSPACE whose definitions are robust across different choices of reference model. In algorithmic analysis, on the other hand, algorithms are often characterized relative to the finer-grained hierarchy of running times `log_2(n)`, `n`, `n log_2(n)`, `n^2`, `n^3`, ... within P. Source: https://plato.stanford.edu/entries/computational-complexity/ https://plato.stanford.edu/entries/computational-complexity/ Note: I've done some light edits so the mathematics are roughly in LaTeX syntax; e.g. `_` for subscripts.