Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Help me turn this into a Big O

Name: Anonymous 2012-06-12 17:31

Hey /prog/... today the idea of reciting the alphabet backwards came up in conversation, and this led rise to me thinking about the complexity of doing so. Unless one mentally remembers which letter comes before which, trying to get perfect accuracy may end up with the same complexity of printing a linked list string in reverse. The end result is that the time will be equal to the sum of the number of characters and the sum of every other amount of characters before it. In other words, on a normal alphabet, 26 + 25 + 24 + ... + 2 + 1.

What I'm trying to do is simplify this into a Big O notation. At the moment, I've got some awkward formula of O(f(n)) = O(n^2 + f(n-1)), or something like that.

I'm curious to know if anyone knows how to simplify this.

Name: Anonymous 2012-06-13 13:58

>>13

Realistically speaking, however, the alphabet is not stored in one's mind like an array. I mean... can you off the top of your head know that that 20th letter of the alphabet is "t"? No, of course not, you typically think about it like a linked list. You always know what letter comes after any given letter, but knowing what letter comes before it takes a bit more thought. Speaking the alphabet backwards is thus like printing a linked list of characters backwards by accessing the individual characters.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List