When somebody says O(n)
, the n
can refer to different things depending on context. When it isn't obvious what n
refers to, people ideally point it out explicitly, but several conventions exist:
- When the name of the variable(s) used in the O-notation also exist in the code, they almost certainly refer to the value of the variable with that name (if they refer to anything else, that should be pointed out explicitly). So in your original example where you had a variable named
n
, O(n)
would refer to that variable.
- When the code does not contain a variable named
n
and n
is the only variable used in the O
notation, n
usually refers to the total size of the input.
- When multiple variables are used, starting with
n
and then continuing the alphabet (e.g. O(n*m)
), n
usually refers to the size of the first parameter, m
the second and so on. However, in my opinion, it's often clearer to use something like | |
or len( )
around the actual parameter names instead (e.g. O(|l1| * |l2|)
or O(len(l1) * len(l2))
if your parameters are called l1
and l2
).
- In the context of graph problems
v
is usually used to refer to the number of vertices and e
to the number of edges.
In all other cases (and also in some of the above cases if there is any ambiguity), it should be explicitly mentioned what the variables mean.
In your original code you had a variable named n
, so the statement "This is O(n)
" almost certainly referred to the value of the parameter n
. If we further assume that we're only counting the number of multiplications or the number of times the loop body executes (or we measure the time and pretend that multiplication takes constant time), that statement is correct.
In your edited code, there is no longer a variable named n
. So now the statement "This is O(n)
" must refer to something else. Usually one would then assume that it refers to the size of the input (which would be the number of bits in m
, i.e. log m
). But then the statement is blatantly false (it'd be O(2^n)
, not O(n)
), so the original statement clearly referred to the value of n
and you broke it by editing the code.
n
in the code, I'd say it's safe to assume that it's referring to that variable. – sepp2k Apr 9 '18 at 16:54n
. But I thinkO(n)
andn
inside the function are different things? – user13985 Apr 9 '18 at 16:56O(n)
to refer to the size of the input in this case, the statement "This is O(n)" would be false. – sepp2k Apr 9 '18 at 17:11