In counting sort time complexity notation O(n+k), k is number of distinct elements?
Time complexity of counting sort is $O(n + k)$ where $n$ is the size of array, and $k$ is the maximum element in the array, not the number of distinct elements. 

For example if we have the array $A = \text{{1, 2, 3, 3, 3, 4, 5, 8, 8}}$ Let's say that for our array $n = 9$ because we have $9$ elements, and $k =8$ because our biggest element is $8$.

Now we create another array $B$ of size $k$ where for each number in the range $[1, k]$ we keep how many times in occurs in the array $A$. $B = \text{{1, 1, 3, 1, 1, 0, 0, 2}}$.

Now we iterate through the array $B$ and for each index $i$ in $B$ we do exactly $B[i]$ iterations. We can see that sum of all numbers in $B$ equal $n$ so we do $k$ iterations in the first for and $n$ iterations in the second for. 

In total the complexity is $O(n+k)$ where $n$ is the size of array and $k$ is the biggest element in the array.