You realize complexity is measured in terms of worse case. So worst case is O(N) if you're iterating through the list. There's no such thing as O(2N) factors drop off in complexity measures.

Very nice. I didn't know Seq.mapi exists unfortunately so I used List.fold2 to the same end. Thing with the bases and shifting is also great. Thank you for new ideas.

This is not best practise. You are counting the letters for every letter.

You will count for one value multiple times.

This is not a good practise since you go through the array twice.