O(n) vs. O(n^2) Startups
79 comments
·May 15, 2025bee_rider
danjl
If only it was exponential in the beginning, as word-of-mouth spreads. Sigh. The reality is that you need to claw and scrape your way to your first customers. The numbers vary depending on whether your product is b2b, consumer, or more niche, but the first customers are the hardest. You rarely get word-of-mouth in the beginning. Instead, it comes much later, typically after a long period of slow growth as you learn more about your customer's workflows and problems and adjust the product to get closer to PMF.
withinboredom
This is actually a better model and one that more closely reflects reality. You can see it on revenue as well, since even if growth is exponential, churn is a percentage of your total paying users. Thus, it produces a sigmoid curve unless you can get churn to 0% (pro-tip: you can’t).
But, these are the two basic levers for a SaaS: growth and churn.
jvanderbot
The first thing I learned when I joined my first business was covered in orientation with leadership: every product or business unit is a sigmoid, and to maintain growth you must add new products or business units without spending too much to do so. Then the overall company profit can grow linearly or whatever by being a sum of sigmoid functions that spawn over time.
Good leadership knows when the flattening will happen and pivots.
This is called "innovation". That really stuck with me as a mental model.
thaumasiotes
> You can see it on revenue as well, since even if growth is exponential, churn is a percentage of your total paying users. Thus, it produces a sigmoid curve unless you can get churn to 0% (pro-tip: you can’t).
Exponential growth means that additional users are a percentage of your total users.
It is trivial to see that adding a source of exponential decay will give you another exponential function. All churn (as you've defined it) does is lower the exponent. It will never take you from exponential to sigmoid.
nis251413
Sigmoid (or the logistic function specifically rather) is exponential until you get close to the "turning point" (or rather, its growth bounded from below by an exponential). It's as you approach that point that it becomes linear, and after that its growth decays.
However you are sort of right that "churn" does not necessarily have to do with it being sigmoid because it will be anyway. It may be bring it earlier if the churn rate surpasses the user growth, but that's probably not important here.
withinboredom
Growth is not a function of users, though, it is a function of something else that *may* be exponential, for a time. Users don’t beget users (word-of-mouth doesn’t last forever; ad money has diminishing returns), and eventually your market will be saturated, so you can’t grow exponentially forever.
godelski
I took the author's use of O(n) vs O(n^2) as a framing point rather than a literal model. It just seems to be missing the forest for the trees. Besides, we can approximate sigmoids with linear or quadratic functions when windowing them. Considering startup as context I think we know what part of the graph we're talking about... Do we see that exponential explosion or is the sigmoid much more flat. Replace the x in your sigmoid with (ax) and is a <1 or >=1?
nis251413
Big-O notation is about asymptotics. You have to approach something, and typically there is some infinity involved because if it is not, then you can just compute things instead of giving asymptotic approximations, or else you have 10^10*n and 0.001*n^2-10^20*n and the big-O asymptotics at infinity are useless for smaller numbers. I understand what OP tries to say but that's not really a good framing point for many reasons. If you want to talk about a finite period of time, use a regression model, not asymptotics. But that's probably also a more personal preference around using mathematics colloquially but also in a manner that is not a good metaphor and does not correspond with what the mathematical theory is referring to. And I am not sure at all whether it is very well understood "what part of the graph we're talking about", in the sense that the modern organization of economy is far from acknowledging the fact that resources on earth are actually finite. Talking about O(n) and O(n^2) or O(exp(n)) as if growth can be indefinite comes with a specific kind of mindset, and the frame used reflects this type of mindset.
godelski
> Big-O notation is about asymptotics.
>> I took the author's use of O(n) vs O(n^2) as a framing point rather than a literal model.
| The reason I borrow the asymptotic notation is because it implies the growth rate is an upper bound (best case scenario) and generalizes away specific constant factors and sums. The analogy breaks down when you force n or n^2 imply something numerically specific about your growth rate, or introduce functions with different growth rates like logs or exponentials. For now we will (somewhat unprincipledly) stick with two sole classes: O(n) and O(n^2).
> If you want to talk about a finite period of time, use a regression model, not asymptotics
>> Considering startup as context I think we know what part of the graph we're talking about...
>> Besides, we can approximate sigmoids with linear or quadratic functions when windowing them.
My point is: you're derailing the conversation
You are technically right, but you're derailing the conversation in an effort to prove your intellectual capabilities to a person who were not questioning them in the first place. You're flexing to the wrong group.
> I understand what OP tries to say but that's not really a good framing point for many reasons.
mgraczyk
They are sigmoids, but for some the plateau is 30 years in the future with a 5T market cap.
For example Facebook's revenue is still increasing at an increasing rate, 21 years later
alangibson
This is an incredibly important thing to understand. Buffet himself said it's better to be an average business in a great market that to be a great business in an average market.
ptero
Interesting. Not doubting this, but one of his sayings I saw many times is that "it is better to buy a great company at a good price than a good company at a great price", implying that great companies are worth significant premiums.
ocean_moist
Yeah sigmoid is good. I kind of hint at this when I mention "saturate their TAM at some rate".
You can think about it like we are looking at the concave up portion of the sigmoid only. The early growth phase.
danjl
> O(n) companies can’t afford to hire the absolute best talent.
O(n) companies tend to have more experienced founders and engineers in my experience. This is partly why they have "nice deadlines, clear SoW" and "understand their customers" enough to have PMF. The strength of their talent, experience and job networks often greatly outweighs the cash incentives, allowing them to hire top candidates. They do not just hire "to fit a job description" because, since money was tighter, they are super conservative about hiring, have always done the job they are hiring for themselves for a long time, and know exactly what they need. It is the O(n^2) companies that hire for job descriptions that fit the positions the VCs tell them they need. I think your experiential datapoints may be too sparse.
Aurornis
In my experience the heavily VC funded companies have a lot of very talented and experienced people, too.
But they have so much money and pressure to hire that they start dipping deeper and deeper into their candidate pipeline. They start lowering their standards to keep the employee count growing. This results in a mix of talented people trying to get work done and a lot of people who are good at interviewing and stretching the truth about their experience.
Every time I’ve been at a company like this, they tell themselves they’ll hire fast and fire fast to compensate. Then they never fire fast or at all, because nobody wants their little empire to shrink.
ryandrake
The vast, vast majority of companies don't need "the absolute best talent." Their product is a JSON interface to someone else's service. You don't need John Carmack to write that. Companies comically overestimate the level of talent they actually need, and let positions stay open for months, sometimes years, looking for that unicorn programmer they don't actually need, and passing up hundreds of candidates who would work out fine.
jbmsf
And also, engineers who are sick of the stupidity that comes from having too much VC money and not enough wisdom to use it.
ocean_moist
Experience != talent. Perhaps a better way to phrase it is that they hire the minimum needing to succeed in a well defined role. Startups aren't afforded this comfort as the roles are not well defined.
fooker
There's an interesting misunderstanding in this article.
The argument for O(n) is well formed here.
O(n^2) is not, the core argument is that these grow faster because of compounding. Compounding is fundamentally an exponential process, far larger asymptotically than a quadratic.
robocat
The article clearly isn't meant to be mathematically correct: you are being over-rigorous in your criticism. From the article:
Businesses generally grow following a few patterns. They generally have some TAM to saturate and saturate the TAM at some rate. This rate can be vaguely linear, what I call O(n), or vaguely superlinear, what I call O(n²). The reason I borrow the asymptotic notation is because it implies the growth rate is an upper bound (best case scenario) and generalizes away specific constant factors and sums. The analogy breaks down when you force n or n² imply something numerically specific about your growth rate, or introduce functions with different growth rates like logs or exponentials. For now we will (somewhat unprincipledly) stick with two sole classes.nine_k
True exponential growth is possible, but I suspect is rare, because the expenses can also compound, so a polynomial growth may be an acceptable approximation. It's also important to remember that "every exponential growth curve is a sigmoid in real life" (can't remember the source of the quotation).
jxjnskkzxxhx
> True exponential growth is possible, but I suspect is rare, because the expenses can also compound
If you have an exponential (revenues) and another exponential of smaller rate (expenses; assume you have profit) then the difference is still an exponential.
ocean_moist
Addressed in the footnotes:
> [2] Perhaps choosing a better two functions could more closely explain the growth dynamics of network effects, which could be more exponential. I think the analogy diminishes in value if you try to directly numerically match it to some growth metric.
vessenes
To quote a private equity investor friend: “I’ve known startup CEOs of billion-dollar companies that are flat broke. Meanwhile people with $50mm/ARR dating sites from Europe live like kings.”
A good reminder that it’s worth deeply understanding venture portfolio economics before you get on the ride. Not that it’s a bad ride. But it’s a ride.
ridiculous_leke
I wonder what's optimal for me as an employee. I am working in a O(n) startup where colleagues are nice, work is streamlined yet challenging, and I do see growth potential in the long term. Several O(n^2) founders have reached out recently and the pay is attractive(even after accounting for a move to an HCOL area).
danjl
Or, really, to say the unsaid bit out loud: there are lots of important considerations when taking a job. The author seems to assume that money is the only driver, when, for many top candidates, money is not their primary motivation. The ability to plan well and thereby reduce stress is a good measure of the management experience. Other non-cash incentives tend to be given out more readily at well-run non-enterprise companies, including remote work, longer vacations, and more strategic control, to name just a few.
null
robocat
Modern society tends to severely overemphasize money as the optimisation goal. This is an emergent behaviour of our good capitalist system.
Your time is precious. You spend it once and you can't predictably get any more of it.
I suggest you choose your optimisation goal function very very carefully to suit the outcomes you want (money is only an intermediate step). It's hard to decide what we really want. Money is the default game that we see our peers playing (and it's easy to gain moderate success at the money game). It requires more attention to find and learn from people that have had success playing less common games.
Cynically (or even conspiratorially) investigate the suggested life defaults for you by your society as though they were dark patterns designed to mislead you.
I like what Naval wrote about status games (money is only one aspect of status). Paraphrased:
Status is a zero-sum game, not a positive-sum game. There’s always a subtle competition going on between status and wealth. For example, when journalists attack rich people or the tech industry, they’re really bidding for status. The problem is, to win at a status game you have to put somebody else down. That’s why you should avoid status games in your life – because they make you into an angry combative person. You’re always fighting to put other people down and elevate yourself and the people you like. Status games are always going to exist; there’s no way around it. Realize when you’re getting attacked by someone else and they’re trying to look like a goody-two shoes. They’re trying to up their own status at your expense. They’re playing a different game. And it’s a worse game.
Money has no maximum so it's a weird goal to try and reach. I wonder why Warren Buffett waited until 95 to decide to retire? He would easily be the richest man in the world if he hadn't charitably given so much away.
Another relevant paraphrased snippet from an interview about better lives for the elite: https://archive.ph/kF0YR
There’s this study called the American Freshman Survey [edit:snip] In the 1960s, 50% of students said making as much money as possible was a really important goal. Today, that’s 80% to 90%. That change shows that this is not human nature. It is culture.curiousgibbon
This is one of the myriad situations where Omega should have been be used, not O. What are they teaching in schools these days?
ocean_moist
I actually passed my discrete math class and final a few days ago and got the big O vs Theta vs Omega question right.
The reality is that companies often underperform their best case possible growth rate. O(n) and O(n^2) are meant to represent the best possible growth rate which may be practically be underperformed.
You may be thinking about algorithmic analysis where the term "worst case" is used for the upper bound, but here, the upper bound represents the best case. Sort of counter-intuitive but the underlying mathematical notation is properly defined.
curiousgibbon
It's entirely nonsensical to use O as a lower bound though. You could have two companies no growth whatsoever in value and correctly state that one has O(n) growth rate and the other has O(n^2) because a constant is both O(n) and O(n^2) (and O(n!) and O(exp(n^n)) ...). The author is trying to argue that there's some separation between two hypothetical startups' growth rates and as such an upper bound on one, say O(n), and a lower bound on the other, say Omega(n^2), is warranted. It sounds like you're not entirely an expert despite your recently-passed final. Strange concept, eh?
ocean_moist
I am actually the author.
You're right that mathematically, a function with constant (or no) growth is O(n)and also O(n^2), and O(anything_that_grows_faster).
My use of "O(n) startup" and "O(n^2) startup" is intended to classify the type of business based on its *inherent best-case growth potential or ceiling*.
An O(n) startup in my framework is one whose fundamental business model, market, or structure means its growth, even in its best-case scenario, is capped at roughly linear. It cannot achieve sustained super-linear growth; its upper bound is linear.
An O(n^2) startup is one whose model (e.g., strong network effects) has the potential for super-linear (which I've simplified to n^2) growth as its best-case scenario. It might be underperforming (even flat, and thus also technically O(n) in that moment), but its design allows for a fundamentally different, higher growth ceiling. The whole point is illustrate potential withholding implications or conclusions from its current growth rate, which is necessary at a companies inception.
So, yes, a flat-lining "O(n^2) type" startup would currently show growth that is O(c) (and thus also O(n)). But the point of my labels is to say that an "O(n) type" startup, by its very nature, cannot achieve the n^2 best-case that the other type can, even if both are struggling.
The labels describe the class they have, dictating their asymptotic best-case limit, not just any loose upper bound on current, possibly sub-optimal, performance. The separation I'm arguing for is based on that fundamental difference in their potential trajectory’s ceiling.
If I used Omega this would imply the actual growth rate of the startup would have to strictly be better n or n^2.
TypingOutBugs
The author is an early CS bachelors student so… they might still learn this in school
sshine
Since O(n^2) is used as a proxy for “something superlinear, but don’t get hung up on how much”, you might also choose O(n^(1+ε)), an upper bound characterised by some arbitrarily superlinear function.
brap
Why not O(nlog*(n)) startups
sshine
Because, as the article states,
> The analogy [between asymptotic growth and company economic growth] breaks down when you force or imply something numerically specific about your growth rate, or introduce functions with different growth rates like logs or exponentials. For now we will (somewhat unprincipledly) stick with two sole classes: O(n) and O(n^2). Perhaps choosing a better two functions could more closely explain the growth dynamics of network effects, which could be more exponential. I think the analogy diminishes in value if you try to directly numerically match it to some growth metric.
So the article specifically tries to be unspecific about what superlinearity we're talking about, and also calls it vaguely superlinear. Since O(n^(1+ε)) is arbitrarily superlinear (O(n^1) = O(n), and ε is some arbitrary small amount, making it superlinear by definition, and practically nothing else), it is a good choice when that is all you wish to say.
If you went with O(n log n), you'd get the same questions as with O(n^2): Why not O(...something else...): That's not the point! :-D
sfpotter
Not that it matters, but O(n log n) is often referred to as "quasilinear", but O(n^(1+eps)) is regarded as "superlinear" (and in fact grows faster than O(n log n) for any eps > 0).
ocean_moist
Sure makes sense.
nine_k
> [The conclusion is that] O(n) companies are higher EV than O(n^2) companies. I mean that, on average, a founder will make more money pursuing an O(n) company than an O(n^2) company. And not an insignificant amount, the amount of liquidity and networth a 20m ARR O(n) company is extremely hard to match by a traditional VC backed O(n^2) company.
It's a bit like getting a regular job vs playing a lottery: the former gives you better financial results on average, while the latter gives you a chance to make it really big.
(I also wish it were "linear companies" and "quadratic / exponential companies", or maybe "snooker-cue companies" vs "hockey-stick companies".)
wavemode
> An O(n) startup grows its key metric (revenue, users, etc.) roughly linearly with time—double the time, double the metric. An O(n^2) startup accelerates, with growth compounding super-linearly over time.
Kind of a strange formulation to have n represent the key metric. In algorithm analysis, we would typically have n represent time (or some other cost). So we would say that the startup whose key metrics accelerate exponentially with time is actually an O(log n) startup - they only have to spend (log n) time to get n results.
Maxatar
> In algorithm analysis, we would typically have n represent time (or some other cost).
No, n is never time in any kind of algorithmic analysis. n is a function of the size of the input and the output is some measure of the cost related to the input.
In O(n^2), the size of the input is n and the amount of time, or space, or some measure of the cost has an upper bound that is proportional to n^2.
wavemode
> In O(n^2), the size of the input is n and the amount of time, or space, or some measure of the cost has an upper bound that is proportional to n^2.
Yes, this is my point. In the article, they classify an O(n^2) startup as one which achieves n^2 results in n time, which is the opposite of how the notation is typically used.
danjl
Normally, with big-O notation, the goal is to reduce complexity. The author's wording kinda reverses that assumption only to "surprise" you in the end? A somewhat forced irony.
ocean_moist
Only in algorithmic analysis. Big-O generally is used to describe and classify any arbitrary function.
nis251413
Well, you may want to increase complexity in some contexts, eg in cryptography.
Maxatar
Big-O notation does not have a goal, it's a description not a strategy.
thaumasiotes
>> An O(n) startup grows its key metric (revenue, users, etc.) roughly linearly with time—double the time, double the metric. An O(n^2) startup accelerates, with growth compounding super-linearly over time.
> Kind of a strange formulation to have n represent the key metric. In algorithm analysis, we would typically have n represent time
In the quote you pulled, n is time. If n were the key metric, everything would be ϴ(n).
> So we would say that the startup whose key metrics accelerate exponentially with time is actually an O(log n) startup - they only have to spend (log n) time to get n results.
No, you don't know how the notation is used.
wavemode
> In the quote you pulled, n is time.
It's definitely not. If their usage of O(n) has n as time, then they wouldn't say an O(n^2) startup has accelerated growth of the key metric. You'd be squaring the time, which means slowing down growth of the key metric.
When they say O(n^2) startup they clearly mean a startup which achieves n^2 results in n time. Which is the opposite of how the notation would typically be used.
> No, you don't know how the notation is used.
No, you're confidently wrong.
chubot
Related: Black Swan Farming (2012)
https://news.ycombinator.com/item?id=4497461
https://paulgraham.com/swan.html
It is interesting that YC started as being more Founder friendly ... and I guess "Founder's Fund" did too
But there is still some divergence in interests ... i.e. if you have to make a choice between a safer O(n) path and a riskier O(n^2) path, then the investor prefers the riskier path
Or I'd be very interested in an argument that they don't
dvt
> I think many prospective founders, if their goal is money, should optimize for O(n) businesses from day 1.
Honestly, I don't think anyone "picks" the kind of business they want to run. You just kind of go with the flow. If you raise VC money, you follow their lead, if you're running a small bakery, you'll do whatever makes sense there.
So while this is a fun intellectual exercise, it's an exercise in hindsight. In the moment, you're really just trying to survive the day-to-day and not really "optimizing" for a specific growth pattern.
ocean_moist
I think any prospecting founder should be able to answer the question "will it always take a fixed amount of work to get each new customer?".
Generally if you have some sort of idea of what you want to do, you'll be more successful at it.
scarface_74
Most founders - especially vc backed founders - only care about whether the optics look good enough for an acquisition or an IPO. They could care less if it fails after that.
YC backed companies are no exception
https://medium.com/@kazeemibrahim18/the-post-ipo-performance...
ark296
VC-land is a strange place with strange laws. If you stay in it for too long, you forget that most of the world doesn't follow the power law, and that most of the VC-reasoning just does not help.
Huh.
Not working in the field, I assumed startups went like sigmoids (everything is a sigmoid after all).
Exponential at first as word of mouth spreads, then linear as your users start bumping into each other and word of mouth stops working, and then you eventually start leveling off near carrying capacity (you’ve hit your addressable market).
I thought the game was to try to get bought by some massive company while you are in the linear phase (where you are big enough to be treated seriously but your growth rate still looks absurdly high).