Q:

Complexity measurement in algorithms using auto-initialized arrays

When it comes to evaluate the time complexity of an algorithm which uses an array that must be initialized, usually it is expressed as O(k). Where k is the size of the array.
For instance, the counting sort has a time complexity of O(n + k).
But what happend when the array is automatically initialized, like in Java or PHP. Would it be fair to say that the counting sort (or any other algorithm that needs an initialized array) in Java (or PHP...) has a time complexity of O(n)?

A:

Are you talking about this http://en.wikipedia.org/wiki/Counting_sort which has an time complexity of O(n + k)?
You have to remember that time complexity is determined for an idealised machine which doesn't have caches, resource constraints and is independent of how a particular language or machine might actually perform.
The time complexity is still O(n + k) 
However in a real machine that the initialisation is likely to much more efficient that the incrementing , so n and k are not directly comparable.  The pattern for initialisation is like to be sequential and very efficient (the n). If the counts are of type int for example, the CPU could be using long or 128-bit registers to perform the initialisation.
The access pattern for counting is likely to be relatively random and for large values of k likely to be much slower. (up to 10x slower)

