←back to thread

A visual introduction to big O notation

(samwho.dev)
688 points samwho | 1 comments | 24 Aug 25 07:39 UTC | HN request time: 0.211s | source
Show context
fracus ◴[25 Aug 25 20:02 UTC] No.45018314[source]▶
Having gone through electrical engineering, I always felt that Big O notation was never properly explained unless I happened to miss every time it was introduced. It always felt like it was just hand waived as something we should already know. I'm curious what level of math or computer science is usually responsible for introducing it.
replies(7): >>45018615 #>>45018641 #>>45019080 #>>45020045 #>>45021112 #>>45027527 #>>45029029 #
leni536 ◴[25 Aug 25 20:33 UTC] No.45018641[source]▶
A function f(x) is said to be O(g(x)) if f(x)/g(x) is bounded, that is there is some C so that for every x, f(x)/g(x) < C .

In computer science f(x) is often some complexity function, like number of some specific operations when running an algorithm to completion.

replies(2): >>45020166 #>>45020570 #
1. blt ◴[25 Aug 25 23:44 UTC] No.45020570[source]▶
This needs to be refined: f(x) is O(g(x)) if there exists some X >= 0 such that f(x)/g(x) is bounded for all x > X.

Otherwise, we cannot say that 1 is O(x), for example.