Clever Geek Handbook

Is this algorithm O (1)?

Is the following algorithm just O (1) or is the complexity harder to define?

for (i = 0; i < n; ++i)
    if (i > 10)
        break;

I'm confused by the fact that it is obviously O (n) when n <= 10.

+3


source to share


2 answers


It's O (1) because it takes constant time regardless of the size of the input (n). Speaking of this, O (n) when n <= 10 does not make sense, since the notation for large oh is defined in terms of the growth of an asymptotic function, i.e. For n "large" or more, some value. This is because the actual value of n is irrelevant for the asymptotic complexity: it is a way of comparing different algorithms to each other.



Just take a look at the definition in big-oh format: the function f (n) is O (g (n)) if there is a constant c> 0 and a positive integer m, so f (n) <c * g (n) for n> m. In your case, f (n) is the time it takes to run your algorithm, g (n) = 1, m = 10, and c is proportional to the time it takes to loop through 10 integers.

+5


source


Yes, it's O (1). This is equivalent to being O (1) and saying that it is bounded. The running time of this code is limited, so it is O (1).



+2


source






More articles:


All Articles