Perdón por la demora, había quedado perdida esta pregunta.
1) Asumimos que es O(1). Es una operación que implementa el compilador y no hay razón para suponer que depende del tamaño del bloque de memoria que se pide o devuelve.
2) Sí, y como k es una constante conocida, es O(1) y por lo tanto O(max(k,n)) es O(n).
3) Esa es la idea de como resolverlo.
4) Sí, es la regla del máximo o de la suma (supongo que es m en lugar de k).
5) En el primer for hay exactamente k iteraciones y en el segundo exactamente n iteraciones. En ambos cada iteración es O(1). El tercer for es más interesante y es como argumentás. Vamos a ser más genéricos y suponer que k no es una constante. El tiempo de ejecución es
![\sum_{i=0}^{k-1} (c_1 + \sum_{j=1}^{A[i]} c_2) = c_1 k + c_2 \sum_{i=0}^{k-1} A[i]= c_1k + c_2n](https://eva.fing.edu.uy/filter/tex/pix.php/8a5ec5cce47b03c0a43cf80ed4fbfb59.png "\sum_{i=0}^{k-1} (c_1 + \sum_{j=1}^{A[i]} c_2) = c_1 k + c_2 \sum_{i=0}^{k-1} A[i]= c_1k + c_2n")
donde 
es el costo de 
y 
es el costo de la comparación y cuerpo del while. Ambos, y son O(1) por lo que el tiempo del tercer for es O(k + n) o lo que es lo mismo O(max(k,n)).
Por lo tanto el tiempo de ejecución es O(k) + O(n) + O(max(k,n)) = O(max(k,n)) por regla del máximo.