1 Replies - 1225 Views - Last Post: 19 June 2016 - 03:02 AM

#1 harro.rm  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 63
  • Joined: 18-June 16

Can someone please explain this asymptotic analysis for me?

Posted 18 June 2016 - 09:16 PM

I was reading through some class materials and there was an example in the book:

BottleOfBeer(n):
   for i <-- n to i
      sing "i bottles of beer on the wall, i bottles of beer"
      sing "take one down, pass it around, i - 1 bottles of beer on the wall"
   sing "no bottles of beer on the wall, no bottles of beer"
   sing "go to the store, buy some more, n bottles of beer on the wall


The text says the word "beer" is sung three times in every verse... but I see only max of two. Or maybe each sing line is one verse.
Anyways, it says for BottleOfBeer(n) --> it uses 3n + 3 but doesn't give a clear explanation.

So is 3n the number of times "beer" is sang? Whats the other 3 from?

Is This A Good Question/Topic? 0
  • +

Replies To: Can someone please explain this asymptotic analysis for me?

#2 Atli  Icon User is offline

  • Enhance Your Calm
  • member icon

Reputation: 4238
  • View blog
  • Posts: 7,216
  • Joined: 08-June 10

Re: Can someone please explain this asymptotic analysis for me?

Posted 19 June 2016 - 03:02 AM

Quote

i bottles of beer on the wall, i bottles of beer
take one down, pass it around, i - 1 bottles of beer on the wall

I count three.

Quote

So is 3n the number of times "beer" is sang? Whats the other 3 from?

If N is the number of bottles you pass to the function, then the number of times the word "beer" is sung is:
(N * 3) + 3


3 being the number of "beer" in each verse, times the number of verses that are sung, plus 3 for the obligatory end verse.

Another way to look at it would be:
(N + 1) * 3


That number of main verses plus the end verse, times the number of "beer" references per verse.

This post has been edited by Atli: 19 June 2016 - 03:06 AM

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1