1
$\begingroup$

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)?

$\endgroup$
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It means if some fix value is given in such case it will be O(1) ? $\endgroup$ – Vishal Upadhayay Nov 27 '19 at 9:40
  • $\begingroup$ @VishalUpadhayay Yes. $\endgroup$ – Juho Nov 27 '19 at 9:45
0
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.