In a sorting algorithm, While computing the complexity of an algorithm why do we only account for the number of comparisons done but not the number of swappings done? And what's the formal definition of complexity?
4
-
2$\begingroup$ Short answer: because you always perform more comparisons than swaps. $\endgroup$– Yves DaoustJan 31 at 14:35
-
$\begingroup$ The complexity of a sorting algorithm is determined by the number of elementary operations such an algorithm performs. For comparison-based sorting (i.e., insertion sort, merge-sort), the elementary operation is a comparison between two values. However, comparison is not always the elementary operation in sorting algorithms. For example, in counting sort, the elementary operations are assignment of values and addition. $\endgroup$– IqazraFeb 1 at 10:41
-
$\begingroup$ @YvesDaoust, this is not true, e.g. for insertion sort with binary search. $\endgroup$– DmitryFeb 1 at 18:00
-
$\begingroup$ @Dmitry: right, there are rare exceptions. I said "sort answer". $\endgroup$– Yves DaoustFeb 1 at 18:02
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
The formal definition of complexity of an algorithm is the runtime in terms of the length of the input. Meaning, suppose you have a number with size n, to represent the number n you need $log_2(n)$. Thus, the actual time complexity is the runtime relative to $log_2(n)$ bits and not n.
For instance, when computing the complexity of an algorithm, it may run in a linear time in terms of the input size, however, not in terms of the input length.
I would encourage you to read about pseudo complexities. For example, say you have an algorithm that runs in $O(n^2)$, where $n$ is the size of the number. Since you need $log_2(n)$ bits to represent the number n, the algorithm actually runs in an exponential time relative to its representational length in terms of bits.
Why an algorithm that runs in $O(n^2)$ in terms of the numerical value of the input is actually exponential?
As we said, to represent the number $n$, you need $x=log_2(n)$ bits. Thus, this is equivalent to an exponential complexity in terms of x, where x is the number of bits of the numerical value. $O(2^{2x}) = O(2^{2log_2(n)}) = O(n^2)$.
An algorithm that runs in a polynomial time relative to the size of the numerical value of the input, but runs in an exponential time in terms of the size of bits to represent the input are called pseudo-polynomial complexities.
This is why some algorithms which run in polynomial or even linear times aren't considered efficient.
As for your first question, as Yuval and Iqazra pointed out. In comparison-based sorting, the elementary operation is comparing between the input values.
In most comparison-based sorting algorithms, in order to swap two values with each other, you need to first compare them. Thus, in most cases, prior to swapping two values you will first need to compare them. You would need information about these two values in order to decide whether to swap them or not.
Take bubble sort for instance. The number of comparisons is $O(n^2)$, however, the number of swaps could be much less than that.
-
$\begingroup$ I still don't understand what elementary means here ,does "comparison" take more time than "swapping" ? $\endgroup$– DynamiteFeb 3 at 19:05
-
$\begingroup$ Take for instance a comparison-based sorting algorithm. Comparison is the elementary operation, why? This is because you will not perform a swap between two elements if you haven't compared them with each other. In order to swap two elements, you need to know information about them, which is done by comparing these two elements. $\endgroup$ Feb 3 at 20:52
-
$\begingroup$ As for if comparisons take more time than swaps. The short answer is no and yes. If you consider the very formal definition of complexity, then a comparison takes O(f(n)) where f(n) is the sum of number of bits of the two numbers you're comparing. Swap also takes O(f(n)). Unless you're swapping pointers, then it's O(1). In both cases, we can take the comparison time complexity to be the upper bound of swap time complexity. As I said in my previous comment, in most cases, a swap doesn't occur before a comparison! I will update my answer! $\endgroup$ Feb 3 at 21:08
$\begingroup$
$\endgroup$
Good question. You are right, the running time of an algorithm is defined in terms of the total number of operations.
The reason is because in all standard comparison-based algorithms, the total running time $T$ is always at most some constant times the number of comparisons $P$. In other words, there is some constant $c$ such that
$$T \le c \cdot P.$$
Asymptotic running time ignores constant factors, so the two are basically equivalent as far as asymptotics are concerned.
For instance, if you have a comparison-based sorting algorithm that uses at most $P = O(n \log n)$ comparisons, then (assuming it satisfies the assumption above) the total running time will be $T = O(n \log n)$ as well. Usually it is the total running time we actually care about.
So, for these algorithms, whether you count the number of comparisons or the total running time (i.e., total number of operations), you get the same running time. It is often easier to count the number of comparisons.
Finally, there are lower bounds on the running time of comparison-based sorting algorithms. These work by lower-bounding the number of comparisons needed; they demonstrate that $P \ge \Omega(n \log n)$. It follows that $T \ge \Omega(n \log n)$ for all comparison-based sorting algorithms. The proof works by counting the number of comparisons, which is another, secondary reason why people may count the number of comparisons.
