O(n) vs. O(n^2) Startups
rohan.ga
rohan.ga
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).
But, these are the two basic levers for a SaaS: growth and churn.
Good leadership knows when the flattening will happen and pivots.
This is called "innovation". That really stuck with me as a mental model.
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.
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.
You can think about it like we are looking at the concave up portion of the sigmoid only. The early growth phase.
For example Facebook's revenue is still increasing at an increasing rate, 21 years later
> 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. You just responded to something my comment was never about.
> I understand what OP tries to say but that's not really a good framing point for many reasons.
I think it is clear that O(n) vs O(n^2) is really just an analogy so we shouldn’t over-formalize it. But it is interesting to note that a sigmoid could be thought of as looking like either one, depending on when you look at it.
It makes me wonder if there’s some sampling bias that is accidentally being applied. Because, another way of looking at it could be: assume I observe companies only after they hit a particular size. The companies that are still in the exponential growth phase when I notice them; due to the shape of a sigmoid, those are likely heading much a higher carrying capacity. Those that have hit the linear phase before they are large enough for me to see them are not on as good a trajectory.
For wondering, I believe this might help. If we parametrize sigmoid to be 1/(1+e^{-ax}) then our a factor is at play. We're interested in x<=0. When a < 1 then the function becomes flat and much more linear like. The larger a becomes the more quadratic it looks at near the origin (but still x<=0)
I still think the model is naive. Even just a sigmoid is. You need the composition of them and further parameterization. They are good for approximating as you originally suggested but this is similar to using fourier series. It's the fact that you have the three classes of second derivatives allowing you to strongly control the composite function through minimal parameterization and complexity. But that's also why I immediately understood this to be being using in an illustrative way rather than a serious one. I mean realistically so are you.
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.
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.
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.
I can say that for me, at some point, you just really want a team with good vibes and low BS.
I took a 20% pay cut 3 years back and moved from one startup to another because the vibes were better with an older founding team. It was fantastic and we built some amazing stuff at an incredible pace.
That startup recently folded and the original startup reached out and brought me back at 150% comp of the other startup. But day to day I don't enjoy it as much and the vibes just aren't the same with this crew.
My lesson: team vibes are severely underrated and sometimes even more money doesn't make it better.
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.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.
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.
> 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
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.
If you have an exponential (revenues) and another exponential of smaller rate (expenses; assume you have profit) then the difference is still an exponential.
Plot the graph of 2^x - 1.99^x to see what I mean. It stays close to the axis for a while and then suddenly shoots up. Follows the trajectory of quite a few companies now that I think of it.
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.
> [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.
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
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.
Generally if you have some sort of idea of what you want to do, you'll be more successful at it.
YC backed companies are no exception
https://medium.com/@kazeemibrahim18/the-post-ipo-performance...
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.
> 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.
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.
> It's definitely not.
> When they say O(n^2) startup they clearly mean a startup which achieves n^2 results in n time.
How did you manage to write this down without noticing what you were saying?
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.
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.
Kind of like how an O(n^2) sorting algorithm sorts n^2 elements in time n. Right?
(should really be θ rather than O but you get my point)
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".)
> O(n^2) companies hire high agency people. [...] People are generally given a lot of equity to join and as a reward.
O(n^2) is often a matter of ZIRP-VC-powered artificial-growth (e.g., their example of Uber). That also includes hiring a large quantity of people.
For factors in genuine O(n^2) growth, you might be onto something: with structuring culture to leverage employee agency, and for using meaningful equity to help align employees with business success.
Maybe it is a good way for short term profits, but that is just one metric. That kind of dynamic may be harmful in the long term, and in a really big scale.
If it grows at O(n) it is not a startup in the way "startup" is used in Silicon Valley. It is just an ordinary new business.
It's worth noting that starting an ordinary new business is hard. Probably as hard as starting a startup for anyone who has not started a new business a few times before. And maybe harder because most new businesses are undercapitalized and therefore likely to suck up personal capital while startups get to use other people's money.
Perhaps they are harder to start, but they are also vastly more likely to succeed to their O(n^2), and this is not only due to the increased barrier to entry.
That's what I mean when I say, founders are more likely to succeed at O(n) companies.
Very few have successful exits where the owner walks away with life changing money and no obligation.
(For example, you get successful enough that you need a bit of office space. Well, your little business is not going to persuade anyone with nice office space to lease to it alone... Landlords will instead demand the owners personally guarantee the lease, i.e. commit to paying it or go bankrupt trying, even if the business shrinks and no longer needs or can afford the space. So you thought, great, we had a couple years of strong growth. Now you get to commit personally to five years of a huge expense. Congratulations.)
Typically, new businesses don’t get very much credit on favorable terms without established commercial relationships.
Dealing with failing or failed businesses is just not worth the hassle for most established businesses working in the established business market segment.
Silicon Valley is probably different because the business relationships are different. And of course month to month and short lease real estate are an entirely different market segment than triple-net.
A hungry landlord is a landlord who is in dire financial straights.
Good landlords can afford to wait because they are using real-estate to park wealth, not as a means of putting food on the table. Think insurance company reserves and House of Windsor. It is a long play.
I’m assuming there are similar problems with Lyft.
After all cost of customer acquisition is largely dominated by external factors and cost per user mostly linear until close to market saturation.
Now there might be economy of scale intervening at some point increasing the margin per user, which feed back into growth, but on average fast growing startup are cash negative until much later in life.
TLDR I think the implications in the article is inverting cause and effect
VC culture, private equity, and "hyper-growth" mentality has screwed over many good companies that once provided good services to the community. Good paying jobs with excellent benefits and providing upward mobility.
Now the labor benefits are shrinking, company loyalty is gone, customers screwed over, labor exploited with minimal in return, rising cost of living, increasing wage disparity, abuse of powers.
One can argue the neoclassical/neoliberal economic theory and "Reagan-omics" that birthed PE/VC culture gave power to the idiocracy we see today.
I'm getting an impression it's just not profitable enough. For many years I get a feeling that business is considered sound only if it is superprofitable (not exactly the right term, but still) in order to cover all losses.
Probably it's because of market competition required to be at least noticed. Some companies' spendings for marketing are greater than for R&D, production and operations combined. Maybe we got ourselves into a situation where everywhere competing for low-hanging fruits or trying to make customer believe it's the service they need while all of it doesn't really overlap with real society needs.