frontpage.
newsnewestaskshowjobs

Made with ♥ by @iamnishanth

Open Source @Github

fp.

Open in hackernews

What is f(x) ≤ g(x) + O(1)? Inequalities With Asymptotics

https://jamesoswald.dev/posts/bigoinequality/
24•ibobev•3d ago

Comments

josalhor•1h ago
> computer science students should be familiar with the standard f(x)=O(g(x)) notation

I have always thought that expressing it like that instead of f(x) ∈ O(g(x)) is very confusing. I understand the desire to apply arithmetic notation of summation to represent the factors, but "concluding" this notation with equality, when it's not an equality... Is grounds for confusion.

FartyMcFarter•1h ago
Given this possible confusion, is it still valid to say the following two expressions are equivalent as the article does?

f(x) = g(x) + O(1)

f(x) - g(x) = O(1)

qsort•1h ago
I think the confusion is because strictly speaking $f(x) = O(g(x))$ is an abuse of notation. $O(g(n)), \Theta(g(n))$ and friends are sets. We can't say that a function equals a set, or that a function "is less" than another function, but notoriously mathematics runs on javascript, so we try to do something instead of giving a type error.

Here "is less" is interpreted as "eventually less for all values" and "plus a set" is interpreted as "plus any function of that set".

I never liked this notation for asymptotics and I always preferred the $f(x) \in O(g(x))$ style, but it's just notation in the end.

hyperpape•1h ago
Although, when I learned foundations of mathematics, every function was a set, and if you wanted them, you'd get plenty of junk theorems from that fact.
qsort•1h ago
"Everything is an object" is for boys, "everything is the empty set composed with copies of itself via the axiom of pairing" is for men ;)
ndriscoll•1h ago
To me it seems similar to the + C on an antiderivative (or more generally, quotient objects). Technically, you are dealing with an equivalence class of functions, so a set. But it's usually counterproductive to think of it that way (and when you study this stuff properly, one of the first things you do is prove that you (usually) don't need to, and can instead use an arbitrary representative as a stand-in for the set), so you write F(x)+C.
qsort•47m ago
I think the Landau notation is a bit more finicky with the details. When it's really a quotient (like modular arithmetic) I'm with you, but here $O()$ morally means "at most this" and often you have to use the "direction of the inequality" to prove complexity bounds, so I'm more comfortable with the set notation. But again, it's just notation, I could use either.
ijustlovemath•26m ago
Huh, never thought about the potential connection between the set-containment operation and Stokes like that.
ndriscoll•12m ago
It's actually a linear (more generally, abstract) algebra thing. (All, Differentiable, Smooth, or all sorts of other sets of) functions form a vector space. The derivative is a linear operator (generalized matrix). If you have a linear equation y=Ax, then if you can find some solution X, the general solution set is X+kerA, where kerA (the kernel or nullspace) is the set of all v where Av=0. What's the kernel of the derivative operator? Constant functions. So the general solution is whatever particular antiderivative you find plus any constant function.
foxes•57m ago
I feel its not that bad an abuse of notation as kinda consistent with other areas of mathematics -

A coset, quotients r + I, affine subspaces v + W, etc. Not literal sets but comparing some representative with a class label, and the `=, +` is defined not just on the actual objects but on some other structure used to make some comparison too.

sfpotter•3m ago
The reason it's preferred to use "=" instead of "\in" is because the way that Landau notation is generally used in practice is as a kind of ellipsis or placeholder. For example, the Taylor expansion e^x = 1 + x + O(x^2). I could just as well write e^x = 1 + x + ..., but the former conveys more meaning about what is hidden behind the ellipsis. It's an abuse of notation, but in the contexts that it's used, it's not clear what additional clarity using "\in" would bring over "=". Maybe also that big O is mainly used as a notation to facilitate doing calculations, less describing what family a function belongs to. Here are Knuth's thoughts, which I agree with: https://micromath.wordpress.com/2008/04/14/donald-knuth-calc...
edflsafoiewq•47m ago
O(1) just means "a bounded function (on a neighborhood of infinity)". Unlike f(x), which refers to some function by name, O(1) refers to some function by a property it has. It's the same principle at work in "even + odd = odd".

Programmers wringing their hands over the meaning of f(x)=O(g(x)) never seem to have manipulated any expression more complex than f(x)=O(g(x)).

bo1024•35m ago
The easiest way to read it is "there exists a function h in O(1) such that f(x) <= g(x) + h(x)."

I think first we should teach "f in O(g)" notation, then teach the above, then observe that a special case of the above is the "abuse of notation" f(x) = O(g(x)).

dataflow•25m ago
Maybe an easier explanation: just subtract g(x) from both sides.

You get:

  f(x) - g(x) ≤ O(1)
Now, if you already know that

  f(x) - g(x) = O(1)
means "f and g eventually differ by no more than a constant", then

  f(x) - g(x) ≤ O(1)
must mean "f eventually stops exceeding g by a constant".

Shatner is making an album with 35 metal icons

https://www.guitarworld.com/artists/guitarists/william-shatner-announces-all-star-metal-album
20•mhb•42m ago•3 comments

FreeBSD doesn't have Wi-Fi driver for my old MacBook. AI build one for me

https://vladimir.varank.in/notes/2026/02/freebsd-brcmfmac/
223•varankinv•3h ago•181 comments

UNIX99, a UNIX-like OS for the TI-99/4A

https://forums.atariage.com/topic/380883-unix99-a-unix-like-os-for-the-ti-994a/
136•marcodiego•5h ago•45 comments

The Age Verification Trap: Verifying age undermines everyone's data protection

https://spectrum.ieee.org/age-verification
1183•oldnetguy•10h ago•955 comments

AI Added 'Basically Zero' to US Economic Growth Last Year, Goldman Sachs Says

https://gizmodo.com/ai-added-basically-zero-to-us-economic-growth-last-year-goldman-sachs-says-20...
132•cdrnsf•2h ago•92 comments

I Ported Coreboot to the ThinkPad X270

https://dork.dev/posts/2026-02-20-ported-coreboot/
8•todsacerdoti•1h ago•0 comments

Ladybird adopts Rust

https://ladybird.org/posts/adopting-rust/
1059•adius•13h ago•578 comments

What is f(x) ≤ g(x) + O(1)? Inequalities With Asymptotics

https://jamesoswald.dev/posts/bigoinequality/
24•ibobev•3d ago•14 comments

Show HN: PgDog – Scale Postgres without changing the app

https://github.com/pgdogdev/pgdog
185•levkk•9h ago•43 comments

The challenges of porting Shufflepuck Cafe to the 8 bits Apple II

https://www.colino.net/wordpress/archives/2026/02/23/the-challenges-of-porting-shufflepuck-cafe-t...
38•homarp•4h ago•7 comments

Making Wolfram Tech Available as a Foundation Tool for LLM Systems

https://writings.stephenwolfram.com/2026/02/making-wolfram-tech-available-as-a-foundation-tool-fo...
31•surprisetalk•3h ago•20 comments

Show HN: Babyshark – Wireshark made easy (terminal UI for PCAPs)

https://github.com/vignesh07/babyshark
49•eigen-vector•4h ago•26 comments

The Rise of Eyes Began with Just One

https://www.nytimes.com/2026/02/23/science/evolution-vertebrate-eye.html
7•marojejian•7h ago•3 comments

SIM (YC X25) Is Hiring the Best Engineers in San Francisco

https://www.ycombinator.com/companies/sim/jobs/Rj8TVRM-software-engineer-platform
1•waleedlatif1•4h ago

Magical Mushroom – Europe's first industrial-scale mycelium packaging producer

https://magicalmushroom.com/index
353•microflash•17h ago•120 comments

Show HN: Sowbot – open-hardware agricultural robot (ROS2, RTK GPS)

https://sowbot.co.uk/
109•Sabrees•9h ago•38 comments

You are not supposed to install OpenClaw on your personal computer

https://twitter.com/i/status/2025987544853188836
65•bundie•3h ago•30 comments

A simple web we own

https://rsdoiel.github.io/blog/2026/02/21/a_simple_web_we_own.html
176•speckx•9h ago•120 comments

'Viking' was a job description, not a matter of heredity: Ancient DNA study

https://www.science.org/content/article/viking-was-job-description-not-matter-heredity-massive-an...
149•bookofjoe•2d ago•122 comments

ASML unveils EUV light source advance that could yield 50% more chips by 2030

https://www.reuters.com/world/china/asml-unveils-euv-light-source-advance-that-could-yield-50-mor...
252•pieterr•7h ago•65 comments

Lords of the Ring

https://harpers.org/archive/2026/03/lords-of-the-ring-joshua-hunt-cultural-politics-sumo-wrestling/
4•lermontov•3d ago•1 comments

Binance fired employees who found $1.7B in crypto was sent to Iran

https://www.nytimes.com/2026/02/23/technology/binance-employees-iran-firings.html
393•boplicity•5h ago•171 comments

Scent, in Silico

https://www.asimov.press/p/scent
18•surprisetalk•4d ago•1 comments

Benchmarks for concurrent hash map implementations in Go

https://github.com/puzpuzpuz/go-concurrent-map-bench
83•platzhirsch•1d ago•9 comments

Psychology suggests making a shopping list is a sign of sharper thinking

https://economictimes.indiatimes.com/news/international/us/still-making-a-shopping-list-psycholog...
6•ColinWright•37m ago•11 comments

Generalized Sequential Probability Ratio Test for Families of Hypotheses [pdf]

https://sites.stat.columbia.edu/jcliu/paper/GSPRT_SQA3.pdf
25•luu•3d ago•5 comments

Americans are destroying Flock surveillance cameras

https://techcrunch.com/2026/02/23/americans-are-destroying-flock-surveillance-cameras/
563•mikece•6h ago•377 comments

femtolisp: A lightweight, robust, scheme-like Lisp implementation

https://github.com/JeffBezanson/femtolisp
118•tosh•12h ago•14 comments

Elsevier shuts down its finance journal citation cartel

https://www.chrisbrunet.com/p/elsevier-shuts-down-its-finance-journal
525•qsi•16h ago•96 comments

Show HN: AI Timeline – 171 LLMs from Transformer (2017) to GPT-5.3 (2026)

https://llm-timeline.com/
134•ai_bot•16h ago•49 comments