The image attached contains a sorting problem and its solution. I'm having a hard time understanding the very last bullet point of the solution in determining Big O.
Why do we need to compare as well as sort? Isn't sorting inclusive of string comparison already?
I'm confused by why this part is essential, and how we got to the below Big O formula:
You should also take into account that you need to compare the strings. Each string comparison takes 0 (s) time.
On
String comparison is required because the algorithm not only sorts each individual string, but also the entire array of strings.
Consider, for example, the following array of strings:
strArray = ["fish", "cat", "dog"]
The given algorithm first sorts each individual string, which would result in
strArray = ["fhis", "act", "dgo"]
which takes $\mathcal O(a*s\log s)$ time. In this case, $a = 3$ since there are $3$ strings in the array, and $s = 4$ since the length of the largest string, i.e., "fish", is $4$.
Next, the algorithm sorts the entire array which results in
strArray = ["act", "dgo", "fhis"]
This step compares each individual character when sorting two strings. For example, when sorting "act" and "fhis", first a is compared with f, then c with h and so on. This takes $\mathcal O(s)$ time since the length of the largest string is $s$ and comparing two characters is constant time. Therefore, sorting the entire array takes $\mathcal O(a*s\log a)$ time.
Normally, sorting an array of numbers takes $O(n\log n)$. However, in case you are sorting an array of string, it takes $O(s\cdot nlog n)$, where $s$ is the length of the string. This is because when you are sorting an array of numbers, say $[1, 3, 2, 1]$, you swap elements by comparing them. And comparing numbers takes $O(1)$ time. However, in case of an array of string, comparing which string is lexicographically larger takes $O(s)$ time, For example $[abcde, abcdf, abceg]$, when comparing two strings, say $abcde$ and $abcdf$, you are comparing them characters by characters. So it takes $O(s)$ time.