# Time complexity to sort 100 elements by using selection sort?

What will be time complexity for sorting 100 elements using selection sort answer given is O(1), but selection sort time complexity is O(n^2) in every case so how O(1)?

## 2 Answers

That's because you only have a constant number of elements, in this case 100. In other words, $$100^2 = O(1)$$, i.e., you do a constant amount of work. Usually it is more interesting to analyze the scalability of an algorithm with a growing input size $$n$$.

• It means if some fix value is given in such case it will be O(1) ? Nov 27 '19 at 9:40
• @VishalUpadhayay Yes.
– Juho
Nov 27 '19 at 9:45

Let the constant $$c_i$$ denote the cost of the $$i$$th statement of your selection sort algorithm. If $$n$$ is the number of elements in the input array, it is possible to show that the running time of the selection sort algorithm is a quadratic function $$T(n) = an^2+bn+c$$ for some constants $$a, b, c$$. Hence, selection sort is $$O(n^2)$$. Now if you fix $$n=100$$, then $$T(100)$$ is some constant independent of $$n$$ and hence is $$O(1)$$.

Recall that $$f(n) = O(1)$$ if there exists a constant $$c > 0$$ such that $$f(n) \le c$$ for all sufficiently large $$n$$. Every constant function is $$O(1)$$. For example, $$5000 = O(1)$$ because $$5000 \le 5000 \cdot 1$$ and so we can take $$c = 5000$$.