3 ms·
> 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, wit
by wavemode 1y ago
> 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.
- thaumasiotes 1y ago>> 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 1y ago> 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.
- thaumasiotes 1y ago>> In the quote you pulled, n is time. > 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?
- danjl 1y agoNormally, 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 1y agoOnly in algorithmic analysis. Big-O generally is used to describe and classify any arbitrary function.
- thaumasiotes 1y agoYou learn about it in real analysis, but it's worth noting that in analysis you pretty much always use little-O, which is the one that makes the guarantee you need in that context.
- Maxatar 1y agoBig-O notation does not have a goal, it's a description not a strategy.
- nis251413 1y agoWell, you may want to increase complexity in some contexts, eg in cryptography.
- Maxatar 1y ago> 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 1y ago> 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.