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)?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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$.
-
$\begingroup$ It means if some fix value is given in such case it will be O(1) ? $\endgroup$ Nov 27, 2019 at 9:40
-
$\begingroup$
$\endgroup$
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$.
