Csdrhrt

This question is just for fun. I hope it's received in the same goofy spirit in which I wrote it.

I just had the pleasure of reading Knuth's "The Complexity of Songs" and I thought it'd be hilarious if someone could do an analysis of the complexity of an infinite version of "The Baby Shark Song" or two, similar to the one done in ibid. on "O' McDonald had a Farm".

Here are the lyrics:

"Baby shark, doo doo doo doo doo doo.

Baby shark, doo doo doo doo doo doo.

Baby shark, doo doo doo doo doo doo.

Baby shark!

"Mommy shark, doo doo doo doo doo doo.

Mommy shark, doo doo doo doo doo doo.

Mommy shark, doo doo doo doo doo doo.

Mommy shark!

"Daddy shark, doo doo doo doo doo doo.

Daddy shark, doo doo doo doo doo doo.

Daddy shark, doo doo doo doo doo doo.

Daddy shark!

"Grandma shark, doo doo doo doo doo doo.

Grandma shark, doo doo doo doo doo doo.

Grandma shark, doo doo doo doo doo doo.

Grandma shark!

"Grandpa shark, doo doo doo doo doo doo.

Grandpa shark, doo doo doo doo doo doo.

Grandpa shark, doo doo doo doo doo doo.

Grandpa shark!

"Let's go hunt, doo doo doo doo doo doo.

Let's go hunt, doo doo doo doo doo doo.

Let's go hunt, doo doo doo doo doo doo.

Let's go hunt!

"Run away, doo doo doo doo doo doo.

Run away, doo doo doo doo doo doo.

Run away, doo doo doo doo doo doo.

Run away!

"Safe at last, doo doo doo doo doo doo.

Safe at last, doo doo doo doo doo doo.

Safe at last, doo doo doo doo doo doo.

Safe at last!

"It's the end, doo doo doo doo doo doo.

It's the end, doo doo doo doo doo doo.

It's the end, doo doo doo doo doo doo.

It's the end!"

Possible schema:

Let $D=text{"doo"}^6$.

Let $R(x)=x, D,, x, D,, x, D,, x$.

Let $$begin{align}
S_b&=text{"baby shark"},\
S_m&=text{"mommy shark"},\
S_d&=text{"daddy shark"},\
S_{gm}&=text{"grandma shark"},\
S_{gp}&=text{"grandpa shark"},\
H&=text{"let's go hunt"}, \
R_a&=text{"run away"}, \
S&=text{"safe at last"}, \
E&=text{"it's the end"}.
end{align}$$

Let $U(a, b, c, d, e, f, g, h, i)=R(a)R(b)R(c)R(d)R(e)R(f)R(g)R(h)R(i)$.

A song of order $m$ would be defined as follows:

$$begin{align}
mathscr{S}_0&=epsilon, \
mathscr{S}_m&=U(a, b, c, d, e, f, g, h, i)mathscr{S}_{m-1}
end{align}$$

for $mge 1$.

And so on . . .

The Problem:

I'm not sure how to take it from there.

Thoughts:

It should be simple. In fact, I think the complexity of the song, as defined, is just $O(1)$.

I'm not happy with the current schema, either. The $R(E)$ should go at "the end" instead of interspersed throughout for one thing.

Alternatively . . .

What would happen to the complexity of the song if we insist that, instead, we go from $R(text{"baby shark"})$ to $R(text{"grandpa shark"})$ as at the beginning but then, with $$V_ell(S_{gm}, S_{gp})=R(G_ell S_{gm})R(G_ell S_{gp}),$$ where $G_ell=text{great}^ell$ for $ellge 1$, we just carry on with the $V_ell$s?

Again, I suspect that it's $O(1)$, but I believe this much less than I do in the first case.

Please help :)