You are probably familiar with the children\'s song \"Old MacDonald Had a Farm.\

Question

You are probably familiar with the children's song "Old MacDonald Had a Farm." The first verse is

Old MacDonald had a farm, eee-eye, eee-eye, oh.
And on that farm he had a cow, eee-eye, eee-eye, oh.
With a moo-moo here and a moo-moo there,
Here a moo, there a moo
Everywhere a moo-moo,
Old MacDonald had a farm, eee-eye, eee-eye, oh.

In successive verses, more animals are added, and the middle refrain gets longer and longer. For example the second verse is:

Old MacDonald had a farm, eee-eye, eee-eye, oh.
And on that farm he had a pig, eee-eye, eee-eye, oh.
With an oink-oink here and an oink-oink there,
Here an oink, there an oink
Everywhere an oink-oink,
With a moo-moo here and a moo-moo there,
Here a moo, there a moo
Everywhere a moo-moo,
Old MacDonald had a farm, eee-eye, eee-eye, oh.

If singing this song is the algorithm, and the work unit is singing one syllable, what is the exact running time of the algorithm? (Perform an exact analysis for singing n verses.)

If singing this song is the algorithm, and the work unit is singing one syllable, what is the order of magnitude of the algorithm?

Explanation / Answer

Suppose work unit in singing one syllable is 1 work unit. And let there be X syllable in first verse.

Now according to question middle refrain gets longer and longer with successive verses. So, we can assume that number of syllable increases by some constant C. There are N such verse. Hence we can deduce that

For 1st verse total work unit=X

For 2nd verae total work unit=X+C

For 3rd verse total work unit=X+2C

.

.

.

For Nth verse total work unit=X+NC

Thus, total unit work for whole poem will be=X+(X+C)+(X+2C)+...+(X+NC)

= X(1+(1+C)+(1+2C)+..+(1+NC))=X(N+1)(2+NC)/2

So, the exact running time of algorith will be X(N+1)(2+NC)/2.

The order of magnitude of the algorith willl be O(N^2). i.e of quadratic order.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.