Is the computational complexity of counting runs in cribbage O(N*log(N)) in the worst case?

Question

In the card game cribbage, counting the runs for a hand during the show (one of the stages of a turn in the game) is reporting the longest increasing subsequence which consists of only values that increase by 1. If duplicate values exist are apart of this subsequence than a double run (or triple, quadruple, et cetera) is reported.

Some examples:

("A","2","3","4","5") => (1,5) Single run for 5

("A","2","3","4","4") => (2,4) Double run for 4

("A","2","3","3","3") => (3,3) Triple run for 3

("A","2","3","4","6") => (1,4) Single run for 4

("A","2","3","5","6") => (1,3) Single run for 3

("A","2","4","5","7") => (0,0) No runs

To address cases that arise with hands larger than the cribbage hand size of 5. A run will be selected if it has the maximum product of the number duplicates of a subsequence and that subsequences length.

Some relevant examples:

("A","2","2","3","5","6","7","8","9","T","J") => (1,7) Single run for 7 ("A","2","2","3","5","6","7","8") => (2,3) Double run for 3

My method for finding the maximum scoring run is as follows:

1. Create a list of ranks and sort it. O(N*log(N))
2. Create a list to store the length of the maximum run length and how many duplicates of it exist. Initialize it to [1 duplicate, 1 long].
3. Create an identical list as above to store the current run.
4. Create a flag that indicates whether the duplicate you've encountered is not the initial duplicate of this value. Initialize it to False.
5. Create a variable to store the increase in duplicate subsequences if additional duplicates values are found after the initial duplicate. Initialize it to 1.
6. Iterate over the differences between adjacent elements. O(N)
7. If the difference is greater than one, the run has ended. Check if the product of the elements of the max run is less than the current run and the current run has length 3 or greater. If this is true, the current run becomes the maximum run and the current run list is reset to [1,1]. The flag is reset to False. The increment for duplicate subsequences is reset to 1. Iterate to next value.
8. If the difference is 1, increment the length of the current run by 1 and set the flag to False. Iterate to next value.
9. If the difference is 0 and the flag is False, set the increment for duplicate subsequences equal to the current number of duplicates for the run. Then, double the number of duplicates for the run and set the flag to True. Iterate to the next value
10. If the difference is 0 and the flag is True, increase the number of the runs by the increment for duplicate subsequences value.
11. After the iteration, check the current run list as in step 7 against the max run and set max run accordingly.

I believe this has O(N*(1+log(N)). I believe this is the best time complexity, but I am not sure how to prove this or what a better algorithm would look like. Is there a way to do this without sorting the list first that achieves a better time complexity? If not, how does one go about proving this is the best time complexity?

iterate over the differences between

Answer 1

Time complexity of an algorithm is a well-traveled path. Proving the complexity of an algorithm varies slightly among mathematician clusters; rather, the complexity community usually works with modular pseudo-code and standard reductions. For instance, a for loop based on the input length is O(N) (surprise); sorting a list is known to be O(log N) at best (in the general case). For an good treatment, see Big O, how do you calculate/approximate it?.

Note: O(N x (1+log(N)) is slightly sloppy notation. Only the greatest complexity factor -- the one that dominates as N approaches infinity -- is used. Drop the 1+: it's simply O(N log N).

As I suggested in a comment, you can simply count elements. Keep a list of counts, indexed by your card values. For discussing the algorithm, don't use the "dirty" data of character representations: "A23456789TJQK"; simply use their values, either 0-12 or 1-13.

for rank in hand:
    count[rank] += 1

This is a linear pass through the data, O(N).

Now, traverse your array of counts, finding the longest sequence of non-zero values. This is a fixed-length list of 13 elements, touching each element only once: O(1). If you accumulate a list of multiples (card counts, then you'll also have your combinatoric factors at the end.

The resulting algorithm and code are, therefore, O(N).

---

For instance, let's shorten this to 7 card values, 0-6. Given the input integers

1 2 1 3 6 1 3 5 0

You make the first pass to count items:

[1 3 1 2 0 1 1]

A second pass gives you a max run length of 4, with counts [1 3 1 2].

You report a run of 4, a triple and a double, or the point count

4 * (1 * 3 * 1 * 2)

You can also count the pair values:

2 * 3! + 2 * 2!