Algorithm design

More formally:

Let two functions be given f(n) и g(n) with a natural argument n whose values are positive real numbers. They say that f = O(g) («f grows not faster than g»), if a constant c > 0 exists so that f(n) ≤c *g(n) for all natural n. The notation f = O(g) can be read as «f ≤ g accurate to a constant». Similarly, there are analogs for "≥" and "=" : f = Ω(g) (f grows no slower than g, up to a constant) means g = O (f); f = Θ (g) (f and g have the same growth order) means that f = O(g) and g = O(f).

«Big O» notation is ubiquitous in the literature and general communications about blockchains as well as in general computer science. For example, Kiayias et al. (2016) develops new, more efficient algorithm for «proving PoW» in Bitcoin; here and here «Big O» notation is used to discuss scaling Bitcoin transaction volume; here time complexity of Paxos vs. PoW is discussed; and here time complexity of cryptographic functions is described. It relates to the basic grammar of computer science.

Another important concept, which often is mentioned when computational hardness is discussed in the context of blockchains, is P/NP problems. Good introduction to the topic is on the Wikipedia; here NP-completeness of hash functions is discussed, and in this blog post the author describes importance of «P vs. NP» for PoW consensus sustainability. NP-hardness is the key concept to understand modern PoW algorithms: see, for example, Loe & Quaglia (2018) short research paper or read the whole dissertation; or Ding (2019). If you need more information on «P vs. NP», you definitely need to refer to one of the most influential books in computer science.

First of all, there is absolutely awesome resource to learn in details and experiment with these and many other algorithms. Then, as usual, several links extending what was mentioned in the video: