how do you calculate the complexity in Big-O notation? can any body explain that on this code below

Question

void KeyExpansion(unsigned char key[N_KEYS], unsigned int* w)
{
    unsigned int temp;
    for(int i=0; i< N_KEYS; i++)
    {
        w[i] = (key[N_KEYS*i]<<24) + (key[N_KEYS*i+1]<<16) + (key[N_KEYS*i+2]<<8) + key[N_KEYS*i+3];
    }

    for(int i = 4; i< EXPANDED_KEY_COUNT; i++) 
    {
        temp = w[i-1];
        if(i % 4 == 0)
            temp = SubWord(RotWord(temp)) ^ Rcon[i/4];

        w[i] = temp ^ w[i-4] ;
    }
}

Answer 1

Big-O helps us do analysis based on the input. The issue with your question is that there seems to be several inputs, which may or may not relate with each other.

Input variables look like N_KEYS, and EXPANDED_KEY_COUNT. We also don't know what SubWord() or RotWord() do based on what is provided.

Since SubWord() and RotWord() aren't provided, lets assume they are constant for easy calculations.

You have basic loops and iterate over each value, so its pretty straight forward. This means you have O(N_KEYS) + O(EXPANDED_KEY_COUNT). So the overall time complexity depends on two inputs, and would be bound by the larger.

If SubWord() or RotWord() do anything special that aren't constant time, then that would affect the time complexity of O(EXPANDED_KEY_COUNT) portion of code. You could adjust the time complexity by multiplied against it. But by the names of the methods, it sounds like their time complexity would be based on the length of the string, would would be yet another different input variable.

So this isn't a clear answer, because the question isn't fully clear, but I tried to break things down for you as best as I could.