[mdxn]

I'll ignore discussion as to what counts as a step, what "n" is, or how it doesn't necessarily reflect on the real world. I still feel like this article focuses on the wrong thing. It's equivocating Landau notation (Big O) with complexity/efficiency, but never explains what complexity is. It then proceeds to link this to the efficiency of code under certain circumstances. While this work gives a couple of examples as to how to determine the "big O" of simple algorithms, it ignores its meaning and context. This is a huge mistake.

First off, big O notation wasn't created with complexity theory or algorithms in mind. If I recall correctly, it has its roots in complex analysis. The notation was later borrowed as computational complexity was formalized. What happened is that people needed a way to describe the hardness or "logical sophistication" of problems and tasks. Looking into the asymptotic behavior of a complexity measure was just one means that they used. There are plenty of other ways to do this. The article reads like big O exists for the purpose of complexity analysis of algorithms. I doubt the author intended this, but they should be a bit more careful.

Time and space aren't the only resources of interest. Sometimes you need to quantify how much information you have or how much entropy there is. If you want to understand "what is basically happening", this is something you should pay attention to. Are we handling more information than we have to? What do we need and not need? Circuit sizes, sophistication of proofs, setups of databases, and the complexity of communications/protocols also play a role.

Even ignoring all this, the article is missing an elementary half of the picture: the structure of the input. It's not just about code and its design. Data structures matter, too. How information is organized, how it is encoded, and how it can be manipulated (computed on) makes an absolute huge difference. Are things sorted or unsorted? What kind of list or tree structure is your code working with? From what I understand, this is the whole point of a significant chunk of the interview questions candidates are presented with. It's ridiculous to omit this when introducing algorithmic complexity.

The author claims that Big O notation is an "awesome, not-boring kind of math where you get to wave your hands through the details and just focus on what's basically happening". They are hand waving not just the math, but also hand waving (and ignoring) most of the context as well. It doesn't even directly explain why big O notation models code efficiency in a fruitful way. It just mentions run time and memory usage superficially. In my opinion, this needs to be significantly revised or rewritten.

[scott_s]

The article reads like big O exists for the purpose of complexity analysis of algorithms. I doubt the author intended this, but they should be a bit more careful.

I see no problem with this. My first taste of algorithm analysis was in a freshmen year course, where we were taught the phrase "big oh" and how to analysis algorithms in quite a similar fashion as this article. The idea was to give us the briefest of introductions of the topic, just enough so we could talk intelligently about the elementary data structures we were being introduced to (vectors, lists, trees). We didn't get the real deal until senior year.

"Education is a series of small lies", is what my intro to computer engineering professor said when he said that, actually, some circuits are ternary, not binary.

Basically, the author is trying to introduce a concept to the reader. I don't fault him for not heaping the entirety of an area into an introduction.

[mdxn]

I get the gist of what you are saying and agree with some of it. I still think the article isn't sufficient, at all, for even an elementary introduction to anything. It's incredibly incomplete. An introductory cs course is going to present asymptotic complexity analysis (written using Landau notation) as one of the TOOLS for thinking about the efficiency of code. It will hopefully not just hop to big O without setting up the context. The author can fix this by just reworking the preface. It needs to answer the question: "why are we doing this and how will this accomplish anything?"

If you fail to frame the context and the semantics well enough, you'll end up with people running around saying that an algorithm is "big O of blah." AGH

The introduction to the concept is articulated by the following comparison:

'We want to measure code efficiency. Big O notation describes this. Here are some examples.'

vs.

'We want to measure code efficiency. We can do this by thinking about its usage of resources (complexity). for example, total run time and memory usage. One of the ways to compare the efficiencies of algorithms is to compare their asymptotic behaviors. We can express this using big O notation. Here are some examples.'

-----

The author talks about how big O notation is awesome because you can drop the constants. It is not explained why this is awesome or useful. Interestingly, it later says that sometimes it isn't good because the constants sometimes matter. What is the reader supposed to understand here?

There's no followup as to what to think about after you determine the "big O" of an algorithm. Either he forgot to write this or figured that it was obvious at that point. Considering that he didn't sufficiently explain the concept's motivation either, I don't see how an uneducated reader will get a clear picture.