Capital N vs small n in time complexity

I came accross the following question and it made me confused:

A quadratic algorithm with processing time T(n) = cn2 spends T(N) seconds for processing N data items. How much time will be spent for processing n = 5000 data items, assuming that N = 100 and T(N) = 1ms?

What is the difference between N and n in time complexity?

1 answer

  • answered 2019-11-13 09:17 Néstor Carreño Gimeno

    There is no special meaning for capital N vs lowercase letter n in time complexity. In this context n and N are just used as different values for the same variable, it would make no difference if instead of N they gave you x.

    Important, when I use A => B, the => arrow means "A equals to B", or if you prefer "A ends up being B"

    Now, having in mind the original quadratic function T(n) = c*n^2

    1. If N = 100 and T(N) = 1ms then they are telling you that T(100) = 1ms => 1ms = c * 100^2.
    2. What you deduce from the previous statement is 1ms = c * 100^2 => c = 1ms / 100^2.
    3. Now just replace c and n in the original formula that is T(n) = cn2 (being n = 5000):

      T(5000) = (1/100^2) * 5000^2 => T(n) = 2.500‬ms => T(n) = 2,5s