How bad is Exponential Growth? - Computerphile

Exponential growth is a term that's used a lot, but our intuition can play tricks on understanding it. Dr Tim Muller takes us through some examples that demonstrate just how quickly things get out of hand.
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com

[@TheErer1243]

He never said the duckweed doubles every day, in the first part

[@Fanny-Fanny]

Yep, I agree 100%. I double checked as I know this schtick and he either told the thing wrong, or some shifty editing mangled the underlying point of it. Poor effort, either way. Boo!

[@Lachlan.Wright]

The trick is in the question!!!! By not telling you 'it doubles every day'. Lol

[@Afrikoe]

Neither did he tell us the size of the pond.

[@mohammadareeb1289]

@@Afrikoe the size doesnt matter

[@sebastianelytron8450]

@@mohammadareeb1289 Tell women that

[@andmefikri7555]

Lesson learned: If you have a thousand year worth of interest, your money will still be worthless because the world's government would have collapsed a couple of times.

[@NeoKailthas]

Now you get it

[@alexlandherr]

So that one Futurama episode is economically implausible?

[@PaulFisher]

@@alexlandherr you will notice that as Fry was in the tube aliens destroyed the world several times in the background, so clearly the writers accounted for it

[@444haluk]

central banking is there to make your money worstless anyway. They steal from their citizen to fund their war.

[@andmefikri7555]

@@444haluk Inflations are tax on savings.

[@colin15545]

Sorry to be pedantic, and I know that the topic of the video is exponential growth, but in all fairness to the interviewer, when Dr Muller poses the Duckweed question right at the start, he doesn't actually state that it doubles in size every day.

[@veggiet2009]

Just rewatched that segment to doublecheck what happened. My editing eye and ear noticed that most of the initial duckweed story is covered with an animation and his voice doesn't have a very natural flow, my guess is it took multiple takes to tell the story, or the story was much longer, and the necessary piece of information was lost in the edit. Also when the doubling fact is mentioned later, the interviewer doesn't disagree with it and accepts that fact immediately, suggesting that he'd either heard it before, or for other reason accepted it as a 'given'

[@jimihenrik11]

You're right. Funny enough when he asked the question i immediately assumed it would double every day due to the tone of the story. Guess I'm a victim if school math, were the model always is convenient

[@justintime1746]

"I'll get to a year in a minute" .... Do you live in exponential time per chance?

[@Swahhillie]

TIL: Duckweed is the secret to faster than light travel.

[@PS-vk6bn]

Exactly! It covers the milky way with a diameter of ~100000 light years in only one year 🤣!

[@fanrco766]

the issue here is as it gets bigger, the duckweed orb's surface area becomes orders of magnitude smaller than its volume. So in reality the base of the exponential will decrease over time as the fraction that can actually replicate onto the outside world will become a negligible portion of the total duckweed.

[@SupaKoopaTroopa64]

@@fanrco766 I imagine that, in this faster-than-light duckweed scenario, the duckweed orb doesn't grow radially, but rather splits into two orbs of the same size as the original at the end of each day.

[@3dlabs99]

Breaking-news: "Einstein owned by weed"

[@niklaswassermann9971]

@@SupaKoopaTroopa64 very well explained. The idea, indeed, of exponential growth in nature generally is that every unit splits and "shoves" the others into place, so it's not just an outside surface area replication - with that said, seeing how we would be looking at a three dimensional problem as soon as we're leaving the planet, we would have to decide whether to think of the duckweed orb as surface area duckweed only or wether we want it to cover the full volume- which would obviously have massive implications on the algorithm (surface orb duckweed would have its base lowered if we're looking to cover distance, solid ball duckweed would have an exponential problem slowing it down and then depend on the thickness of duckweed growth). Not a useful way to spend your time, but fun to ponder. With that and the surface area model, the growth exceeding the speed of light actually would mimic what the universe is doing in reality - since the universe is accelerating in its expansion (exponential expansion! whoo!), the relative speed of stuff can exceed the speed of light, which unfortunately leaves us with the sad realization that the visible universe is only ever going to shrink with every moment. Relative speeds be damned!

[@mwissel]

Dr Muller's voice is so calming, he should really have his own podcast. I would certainly tune in

[@zippysqrl]

Tune in and then tune out.

[@michaelnichelson3423]

I was about to comment on this! He also has fantastic intonation. I would love to hear more of his voice. Follow your dreams Dr. Muller!

[@TheNeonRaven]

A correction on the travelling salesman problem, in your example it’s not necessarily difficult to prove that you can visit every city in a week, but it might be difficult to prove the opposite. You could try any random path and it might be less than a week, and there is your answer. The actual problem is finding the FASTEST route to visit every city.

[@jschoete3430]

I disagree, the TSP decision version is NP-hard, and doesn't care about the fastest route.

[@TheNeonRaven]

My apologies, I was unaware about the decision version and dug more into it. I still don't fully agree with that statement though. As an example, if I need to visit 5 places, and it takes 3 days to travel to any of these places, it will very clearly take more than a week. You can prove both of these scenarios by finding the distance between each pair of points and then multiplying the maximum distance value by the number of points to prove that it IS possible, or multiplying the minimum distance by the number of points to prove that it ISN'T possible. It's for values that are in between these ranges that are more complex to prove that there ISN'T a solution, but you can use one of many pathfinding algorithms to find a somewhat efficient solution and prove that it IS possible.

[@jschoete3430]

@@TheNeonRaven NP-hardness is a general term, it doesn't reflect the difficulty of specific instances. As an example, the Hamiltonian Cycle problem is NP-hard, but it is trivial for complete graphs. (Much like TSP is NP-hard, although some instances such as the ones you mentioned are trivial.)

[@lostwizard]

Of course, many real world systems aren't actually straight forwardly exponential but rather behave more like a logistic curve. Which is even more brain melty for people than an exponential I think.

[@MrRyanroberson1]

logistic curves are actually the same intuition for why people usually say things like "if it takes two weeks to cover the whole pond then maybe it covers half the pond in ten days", it's just that when you point out literally the root of common intuition, people get confused

[@thijsyo]

What is that intro question? He didn't even mention that the duckweed doubles in size each day when asking the question!

[@ottersdangerden]

sounds like he is a teacher...

[@R_V_]

Or the details were cut to make the video sound more punchy. But there are a few details you shouldn't cut.

[@skyscraperfan]

Exactly. So 10 days could be right, if it doubles every four days.

[@OnlinePseudonym]

Came to the comments to say this

[@AlexdaCunha]

It was a "planned" question... He also knew the answer.. but the idea was to show what the average person thinks

[@Worr]

The example of making the program 100 times faster made me realize why the Big O notation only cares about the biggest factor.

[@veggiet2009]

And whoever says otherwise must be in the pocket of Big O 🤣

[@appa609]

Duckweed on an infinite pond does not grow exponentially. It grows quadratically. Rate of growth is proportional to its perimeter.

[@boldCactuslad]

Sir, I do believe you have forgotten the critical step of modeling your horses as hollow spheres.

[@ErikB605]

I belief that enough water lentils working together could invent faster than light travel.

[@rewrose2838]

Yeah I was wondering that, since starting from one end and growing towards another, the whole "13 days to cover half the pond, another day to cover the full pond" situation wouldn't occur.

[@simonmultiverse6349]

It could be exploding duckweed which propagates the spores more rapidly. If your pond has a colony of exploding ducks, that may greatly increase the propagation rate. Also throw some sodium in the pond. It makes the tadpoles jump. It certainly made ME jump.

[@ErikB605]

@@simonmultiverse6349 You could increase the propagationrate by a billion the growthbehaviour would still be quadratic.

[@mgancarzjr]

How long would it take to cover the Earth? A day longer than it takes to cover half the Earth.

[@jweezy101491]

This is the only correct answer given the lack of needed details in the question. We can only make this answer because we now know the duckweed doubles every day, which was needed information in the first question which was also omitted! What is this person? An expert in exponentials?!?

[@joekerr5418]

ha! recursion

[@samm5571]

boss makes a dollar i make a dime that’s why my algorithms run in polynomial time

[@Kitulous]

in infinite time i put while (true) { } until they pay me

[@mgancarzjr]

good, fast, cheap Pick two.

[@rewrose2838]

@@mgancarzjr 😂 exactly, managers expect all of this in one unicorn full stack developer

[@Hauketal]

@@mgancarzjr in budget within deadline conforming to specifications pick two if you don't pick, you get none

[@mgancarzjr]

@@Hauketal feature creep: What's a specification?

[@karolisr]

This reminds me of the fundamental "laws" of population ecology: 1. Every population has the capacity to grow exponentially. 2. No population can grow exponentially forever.

[@chriswinslow]

Now this is the Computerphile I know and love. What a great video.

[@feo786]

His voice is so calming and soothing.

[@marklonergan3898]

Think you forgot to mention the growth rate there... i'm gonna check back tomorrow to see if the amount of comments pointing this out have doubled! 🤣 Edit: just going through other comments now and seeing how many negative ones there are. This isn't meant to be a serious jab, it's just light-hearted gest.

[@randy7894]

A treat to watch. Thank you.

[@PixelPhobiac]

This is exactly what needs to be taught right now

[@dhoyt902]

Learning to transform series to converge faster and acceleration techniques, I believe are the coolest things I have ever learned in my life.

[@zolv]

In the very first duckweed question it's not said it doubles the size every day - It's mentioned it only after giving an answer.

[@barrotem5627]

Great video as always ❤

[@sohatyi]

The extension to this is often to discard the actual time constant due to exponential and factorial growth in time rendering the actual time constant fairly moot. So in CS we usually use asymtotic notation instead, most commonly big O. O(2^n) and O(n!) being exponential and factorial time respectively. The growth matters rather than the time constants because if we can design an algorithm that grows in O(n) (linear) or O(n lg n) time it's going to always be faster in all but the most trivial of data sizes. Even if your algorithm takes 1,000,000 times longer per iteration, if it only has to iterate O(n lg n) times vs O(2^n) times, as with the Towers of Hanoi example, you only need to go to small data sets before the exponential option loses out. It's a fascinating topic.

[@bobgerac]

Fantastic video

[@mrsmiley631]

A graph of the exponential function would have spoken a thousand words.

[@james__page]

My annoyance at the errors and sloppiness in this video doubled every minute

[@JamienM]

Great video!

[@user-ue1vw6iv3s]

Thanks for commenting , I'll advise you look up to investing and making huge profit in Bitcoin with Samanthaleeward she's currently managing my crypto portfolio and making great return's*

[@user-ue1vw6iv3s]

Contact OnTelegram @Samanthaleeward

[@swoopskee]

fantastic, thank you very much for this video!

[@user-ue1vw6iv3s]

Thanks for commenting , I'll advise you look up to investing and making huge profit in Bitcoin with Samanthaleeward she's currently managing my crypto portfolio and making great return's*

[@user-ue1vw6iv3s]

Contact OnTelegram @Samanthaleeward

[@Alithenius]

I mean, this past year already answered that question for us.

[@Smingleflorp]

And as always, it all comes back to that cooky pizza delivery guy and his foul mouthed, sticky fingered robot friend ☺️

[@MrRyanroberson1]

i think one of the main reasons why basically everyone commenting mentions either the initial not mentioning the doubling rule or the light-speed duckweed is because this seems like pretty familiar content for the numberphile group and there isn't any other real content in this video

[@nnotcircuit010]

he never said it doubles every day. like he just left that out of the question. without it, there would be no way to solve it.

[@yew7607]

Yeah, he left out the size of the pond and the growth rate so it was essentially impossible to solve

[@mujtabahussain7015]

​@@yew7607 why would size of the pond matter if we just had it's growth rate and time it takes to complete whole pond?

[@silkworm6861]

I remember that Futurama episode!

[@thuokagiri5550]

This should be a numberphile video

[@_DarkKnight2301_]

Pretty good given enough time

[@areyoucerealtube]

Yo Dr Muller this lesson is LEGIT! very well explained

[@user-ue1vw6iv3s]

Thanks for commenting , I'll advise you look up to investing and making huge profit in Bitcoin with Samanthaleeward she's currently managing my crypto portfolio and making great return's*

[@user-ue1vw6iv3s]

Contact OnTelegram @Samanthaleeward

[@EyesOfByes]

#CorridorDigital made a really good visualisation on the time it takes to fill the the entire Grand Canyon, with exponential growth of water

[@GODofTimewaste2]

They've made all other sorts of cool things too over the years

[@miroslavhoudek7085]

So this grows a bit like TAOCP, where you full get the front page, somewhat get the foreword, almost get the reading guide but then already on page 1 you are struggling and you don't stand a chance after page 5. Got it.

[@toddmarshall7573]

Who was the bright guy who propositioned his king to trade rice for his service. The deal: place on grain on the 1st square of a chess board on day one; 2 on the second day; 4 on the third day; and doubling until the 64th square was reached. And for extra credit, how many squares did it take before the kind cut of his head.

[@argenisjimenez8118]

288230376151711,744 Kg!! That's impressive.

[@TheNadOby]

It's an legend about inventing chess in India. And I think the head of the wizard was cut before half of the board

[@pettere8429]

Is not the traveling salesman problem factorial time if brute forced? I.e. superexponential?

[@f.f.s.d.o.a.7294]

Yes

[@jms019]

The thing people don’t get is that falling infections (say) is still exponential

[@peppers1758]

How did I get to the numberphile channel

[@realBeltalowda]

Asks exponential questions, leaves out vital information in the question (Doubling rate)

[@z-beeblebrox]

Hey man, if you ask exponential questions, you get exponential answers.

[@SMJSmoK]

@@z-beeblebrox Play exponential games, win exponential prizes.

[@obinator9065]

They cut it out?

[@donaldhobson8873]

You say, the trick is in the question, and then add new info that wasn't in the question. The first place you say "it doubles every day" is 0:56. After the guess at the answer.

[@Bootleg_Jones]

3:51 if you're getting 3 *new* infections for every existing one, wouldn't it be *quadrupling* not tripling? 1+3=4 Or is the original person no longer counted after their infectious period is over?

[@omri9325]

no

[@blockify]

I felt like a genius answering those few questions correctly.

[@simonmultiverse6349]

You FORGOT TO SAY the crucial piece of information: the growth rate. If you say it doubles every day, (which you probably forgot to say) that means that it takes many days to get going, and on the last day it goes from covering half of the pond to covering ALL the pond.

[@juanecheagaray7903]

I think this video belongs in Numberphile to be honest, regardless it was a cool one!

[@code-dredd]

Traveling Salesman is factorial, i.e., n! where n is the number of locations.

[@mixnewton5157]

with DP it's exponential

[@Lachlan.Wright]

The trick is in the question!!!! By not telling you 'it doubles every day'. Lol

[@Cythil]

A other note on interests on banks. You're also competing with inflation of money. Which has been the trend of money. And you interest tend not to cover the inflation if you just storing you money in transfer account or something like that. Why Fry should do is invest in the Cryogenic freezer company. But... in Futurama it was all a mistake he got frozen to being with.

[@patrickjackman8688]

Doesn't this assume brute force approaches only to cracking an exponential problem? Some native cunning could get around it and convert NP into P.

[@pdemosllegaralos520subs2]

a petahertz computer would be a million times faster than a gigahertz computer, not one thousand. Which raises the question: AMD and Intel, what are you guys up to?! We haven't even hit terahertz yet! (Physics and nanonmeter scale processes might have a lot to do with this!)

[@bjornseine2342]

The misuse of "=" is strong with this one.

[@canadiannuclearman]

A better video on exponential growth is the following by Dr. Bartlett. Title: Exponential Growth Arithmetic, Population and Energy, Dr. Albert A. Bartlett

[@RutNij]

Albert Bartlett... look it up on youtube. All you ever wanted to know about exponential growth and its practical appearances.

[@Keex11]

Then again, it doesn't make much difference if a computer shuffles 100 discs or if I do it by hand slowly and meticulously, so there is some catharsis in exponential problems as well.

[@barrotem5627]

In the first question, he didn't say it doubles every day...

[@MAli-wu4rx]

Inspired by the Xeno paradox; if the whole distance is covered in 2 weeks than half the distance should be covered in 2/3 of the 2 weeks time. Because x/2 + x/4 + x/8.........= x so x+x = 2x and there is a total 3x distance .

[@444haluk]

Exponential functions are awesome, they are the best, not the "bad". And the people who say "some people don't get it" are the people who don't get it and project their inability on other people.

[@mytech6779]

Fry's bank account was still open. It had a value of 4.3 billion.... ($0.96 and 2.5%apr for 1000years is 50billion)

[@DavidBadilloMusic]

... points to the chessboard and says: "All I want is for you to put a single grain of rice on the first square, two grains on the second, four on the third, eight on the fourth, and so on and so on and so on, for the full 64 squares."

[@ravindran_1]

Sir i wanna learn how to hack color preddiction game like mantrimal and rxce. I need ur help sir plz help me

[@XFourty7]

13:10 1 Petahertz = 1,000 Terahertz, and 1 Terahertz = 1,000 Gigahertz, so 1 Petahertz = 1,000,000 Gigahertz.

[@skyscraperfan]

Yes, he made so many mistakes in that video. For example he had a unit at one side of the equation, but not on the other side. Also he said that the number of steps doubles with every disk, but he forgot the additional step of moving the largest disk.

[@tpog1]

Luckily most of us have brains that can do error correction for such trivial mistakes.

[@misium]

The duck weed question did not contain the doubling every day information.

[@veggiet2009]

If you listen carefully during that question you'll note that his voice changes unnaturally and is covered over with an image. My guess is that the story was shortened in the edit and this detail was accidentally cut out. Because when the doubling fact was pointed out later Shawn simply accepts it.

[@sundhaug92]

How bad is Exponential Growth? Ask Samy Kamkar

[@xr.spedtech]

I prefer this content over the Tik Tok rip off that is KZbin Shorts

[@koevoet7288]

Did i miss him saying it doubles every day?

[@dragoran149]

Basically, finding a way to use exponential algorithm for your wealth is the way to go, got it!

[@paologinefra4980]

Wren from Corridor would enjoy this video

[@pdemosllegaralos520subs2]

This should be a numberphile video

[@murk1e]

“It doubles every day”…. You didn’t say that……

[@etziowingeler3173]

😂 true

[@appa609]

The stupidest thing is colloquial use of "exponentially" to mean "more than linearly" or even just "a lot"

[@AnotherPointOfView944]

Yes it annoys the bejesus out of me. I have frequently seen news readers say something is growing exponentially, when the graph they have in the background clearly shows it is actually linear.

[@Sam-py9qq]

@@AnotherPointOfView944 well, a linear graph can be correct for an exponential growth if the scale is logarithmic. In fact it's common since it makes the results more readable. Not that newsreaders likely understand that distinction.

[@AnotherPointOfView944]

@@Sam-py9qq These were straight linear graphs. No logarithmic scales here.

[@sagetx]

While we're on improper colloquialisms, decimate means to reduce by a tenth. Most people mean annihilate when they use it. Aaarrrrggghh!

[@TIO540S1]

On the other hand, you may get the right key on the first guess.

[@abo000Saad]

Interesting

[@DmitryBrant]

I like "Black Death" of the universe better than heat death.

[@fanfarorro]

Ackermann function: Come at me bro

[@treyquattro]

a petahertz computer would be a million times faster than a gigahertz computer, not one thousand. Which raises the question: AMD and Intel, what are you guys up to?! We haven't even hit terahertz yet! (Physics and nanonmeter scale processes might have a lot to do with this!)

[@pettere8429]

Because electric signals at those frequencies do not stay put in the conductor.

[@MagicMottsMan]

The guy never explains what's going on in the first question

[@aikimark1955]

seems that weed is superluminal, covering a 100,000 light year diameter galaxy in less than 1 year

[@greyed]

A numder of discs, k. Goes to write the formula, uses n for number of discs. Wauugh!

[@opaocker]

I thought he meant "Peterhertz" well...

[@UncleKennysPlace]

Knows Futurama memes. Awesome.

[@dandan7884]

I'm almost sure I've seen this video before... Hmmm...

[@therflash]

hmm at that growth rate, it's gonna take about ^$#@* days for half the pond to be covered.

[@swagatochatterjee7104]

How could he just frame TSP wrong? TSP specifically adds the constraint that you can only visit a city once. If this constraint is not there, boy, it is easy to solve all thanks to Euler

[@Tassdo]

You're confusing different things. TSP is still NP-hard even if you can visit cities multiple time (in fact in the case of metric TSP there is no point in visiting a city twice, so that constraint is redundant). I guess you're talking about Eulerian path/cycle which doesn't ask to visit every city/vertex once, but every edge in a graph exactly once. This is indeed solvable in polynomial time.

[@obvioustruth]

It wouldn't be possible to cover entire galaxy in 1 year because it would have to spread faster than a speed of light.

[@tubanbodyslammer9125]

Does Europeans actually say r-zero, cause americans call r_0 r-naut

[@dimaryk11]

2048? Look no further than 256 bits lol (I remember the 3b1b sha256 video)

[@romaneviton5087]

Depends on whether it's symmetric keys or not. Symmetric ones and hash functions (AES, sha256) are considered secure at 256 bits, but asymmetric ones like RSA or Diffie Hellman need much longer key sizes

[@PS-vk6bn]

The universe will die a black death 🤣🤣🤣!

[@urgay1992]

Duckweed doubles every day, Initial seed of duckweed is 6 square cm, The size of the pond is 10 square metres. There, now you have all the information about the duckweed problem you need to answer the questions that was left out of the problem statement. (Judging by the interviewers responses I would guess that this information was originally in the problem as stated but mistakenly edited out to abbreviate the conversation.)

[@kwanarchive]

If it would take multiple universe lifetimes to brute force a 2048 bit key... ...then what if the universe is just a simulation that a supernatural being is using to break into another supernatural being's bank account?

[@Bratjuuc]

I don't see everyone being enslaved by some immanent deity, forcing them to do some binary computations

[@kwanarchive]

@@Bratjuuc Why does it have to binary? And how would you know you aren't enslaved?

[@Bratjuuc]

@@kwanarchive I have freedom

[@kwanarchive]

@@Bratjuuc How do you know? If you're part of the program, your belief that you know is a part of that program.

[@Bratjuuc]

@@kwanarchive I don't want to explain obvious stuff, you're clearly have no idea what freedom is.

[@simonmultiverse6349]

YOU HAVE BEEN WATCHING... The Kooky Wacky Trippy Dippy Freak Show. Thank you for your attention.

[@exponentmantissa5598]

There is a story of a man saves a kings life and is told he can have anything he wants. He asks for a chessboard with one grain of wheat on the first square, 2 on the second, 4 on the third and so on. By the last square he will get more grain than the world has produced in of history.

[@psilynt1]

That was only true at the time that story was made. Nowadays we put out over a billion bushels per year with about a million grains per bushel.

[@exponentmantissa5598]

@@psilynt1 Is is till true, there are 1.6 * 10**19 grains on the last square. Assume a grain is 10 mg. which is undoubtedly light but I will use it anyways (100 grains=1 gram). A kg has 10**5 grains and a ton has 10**8 grains. that means there are 160 billion tons on the last chess square and another 160 billion tons on first 63 chess squares and this is a conservative estimate!

[@drawapretzel6003]

Gigahertz to Petahertz? sorry bub, but it goes Giga, Tera, then Peta. You meant Tera, and accidentally made a computer 1,000,000 times faster :P

[@ijustsawthat]

But what if the Ducks eat all the Duck weed ?

[@ophello]

I am super annoyed with how lazy he’s being with rounding his numbers and using equal signs.

[@EgoShredder]

He's also too lazy to eat properly.

[@zzzzzz1039]

The fact that he had to tip-toe around talking about covid is absurd.

[@user-vn7ce5ig1z]

I already know this puzzle and its answer, so I was waiting for the "trick". I had to re-watch to see where he says it doubles every day because it wasn't mentioned. I don't know if he forgot or they edited that bit out, but either way, it's a fail. 🤦 It seems quite a few others caught that too (which is to be expected, but what's odd is how many didn't notice 🤨).

[@julienbongars4287]

1:00 - you didn't say it doubles everyday you cheat!

[@EgoShredder]

Exponential Growth = Too many π consumed 😉

[@Gunstick]

Computerphile: "let's call this number i" Numberphile viewers: "but that's for complex numbers!" 🤣