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?
There is no special meaning for capital
Nvs lowercase letter
nin time complexity. In this context
Nare just used as different values for the same variable, it would make no difference if instead of
Nthey gave you
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
N = 100and
T(N) = 1msthen they are telling you that
T(100) = 1ms=>
1ms = c * 100^2.
- What you deduce from the previous statement is
1ms = c * 100^2=>
c = 1ms / 100^2.
Now just replace
nin the original formula that is
T(n) = cn2(being
n = 5000):
T(5000) = (1/100^2) * 5000^2=>
T(n) = 2.500ms=>
T(n) = 2,5s