Help me turn this into a Big O

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.

Wait... make that O(N^2 - F(N - 1))

O(N * N/2)

????(n²)

>>4
make that ????(????²)

well,

if f(n) = n^2 + f(n - 1), then you can expand it:


f(n) = n^2 + f(n - 1)
     = n^2 + (n-1)^2 + f(n - 2)
     = n^2 + (n-1)^2 + (n-2)^2 + f(n - 3)
     = n^2 + (n-1)^2 + (n-2)^2 + ... + f(1)
     = n^2 + (n-1)^2 + (n-2)^2 + ... + 1^2

Wait a second....

From the pattern of {1, 2, 3, 4, 5} to {1, 3, 6, 10, 15}, we can see that we are multiplying the values by {1, 1.5, 2, 2.5, 3}, which is just multiplying n by (n+1)/2

Thus, we get O(n * 0.5(n+1)), or O(N^2) simplified.

zyxwvutsrqponmlkjihgfedcba

I learned the alphabet in reverse a few years ago while I was bored. You should try it. I wrote it down on a piece of paper then tried to run it through my head without looking, using the paper wherever I got stuck. It only takes one or two days of practicing to get it down from scratch, then I only recited it a few times after that and I've never forgotten it.

s/from scratch//

>>8
So is this a solution for reverse alphabet in O(1) ?

>>10
O(n), I suppose.

abcdefghijklmnopqrstuvwxyz -> z
abcdefghijklmnopqrstuvwxy  -> y
abcdefghijklmnopqrstuvwx   -> x
abcdefghijklmnopqrstuvw    -> w
abcdefghijklmnopqrstuv     -> v
abcdefghijklmnopqrstu      -> u
abcdefghijklmnopqrst       -> t
abcdefghijklmnopqrs        -> s
abcdefghijklmnopqr         -> r
abcdefghijklmnopq          -> q
abcdefghijklmnop           -> p
abcdefghijklmno            -> o
abcdefghijklmn             -> n
abcdefghijklm              -> m
abcdefghijkl               -> l
abcdefghijk                -> k
abcdefghij                 -> j
abcdefghi                  -> i
abcdefgh                   -> h
abcdefg                    -> g
abcdef                     -> f
abcde                      -> e
abcd                       -> d
abc                        -> c
ab                         -> b
a                          -> a

Now imagine going through all of those operations in your head in front of a cop to prove you're not drunk.

void main(){

    char alpha[letters] = {a, ..., z};
   
    for(int i = letters; i > 0;i--){
        print(alpha[i]);
        print("niggers");
    }
}

Shit's = O(n)

>>13
Except this works well only on a array, where arbitrary access is O(1).
We're talking about linked lists, and real life.

>>14

User a fucking stack then... up your ass.

>>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.

use a double linked list then

>>16
It's more like a linked list with some weird caching algorithm - for example, I can tell you the 5th letter is e or the 25th is y without having to step through.