2

Is it O(k*n*log n), where k is the maximum number of characters in any string, because in strings we have to compare the characters unlike in integers where the comparison can be performed in O(1) time? I'm not sure.

moon
  • 33
  • 3
  • In general for the complexity of sort algorithms, the cost of comparing the elements is not taken into account. – Dani Mesejo Mar 30 '20 at 11:52
  • 1
    What makes you think integers can be compared in O(1) time? An `int` is not a fixed n-bit value in Python; it represents an arbitrarily large integer, and can be thought of as a sequence of n-bit values, just like a string is a sequence of characters. – chepner Mar 30 '20 at 11:55
  • 2
    k does not depend on number of items in data, and can be treated as constant, and is therefore hidden by Big-O notation `O(k*n*log n)` is reduced to `O(n*log n)` – Lesiak Mar 30 '20 at 11:55
  • 1
    Consider comparing 2 strings of random lowercase characters. Regardless of their lengths, 25/26 times the comparison need only consider the first character of each. So the comparison time may grow with longer strings, but it's probably a lot closer to O(1) than you think (depending on the data set) – Hymns For Disco Mar 30 '20 at 11:56
  • 4
    @Lesiak The input size is always the total length of all the strings. When you can assume some constant upper bound on the length of any one string, that total length is O(kn)`, and so you can ignore the `k`. When there is no such bound, the length of the strings themselves contribute to the input size, and thus affect the running time. – chepner Mar 30 '20 at 11:57
  • Does this answer your question? [Why is sorting a string O(n log n)?](https://stackoverflow.com/questions/4433915/why-is-sorting-a-string-on-log-n) – metatoaster Mar 30 '20 at 12:00
  • @DaniMesejo But when analysing the time complexity of an algorithm which requires sort of a list of strings as a dominant operation, we cannot say it's O(nlogn), right? – moon Mar 30 '20 at 12:00
  • @dev Again, it depends on the assumption your algorithm makes. The algorithm makes needs to make O(n lg n comparisons). The time it takes to make each comparison determines the overall complexity of the algorithm, and the complexity of the comparison depends on what the algorithm can assume about its input. – chepner Mar 30 '20 at 12:05
  • @chepner No, the problem doesn't express k in advance, it could be arbitrary. Basically I was solving this question: https://leetcode.com/problems/longest-common-prefix/ and used sorting to solve the question. But was not sure about the time complexity. So, what will be it's time complexity? – moon Mar 30 '20 at 12:16

0 Answers0