Não sei se perdi algo, mas esses códigos parecem esquisitos, e talvez não ajudem tanto entender a questão, pelo contrário.

Importante dizer que não é porque um loop é O(n), todos serão. Pode ter complexidade escondida, ou até interrompida e ser diferente. A operação de impressão é O(1) sob o olhar externo. Dentro da impressão tem outro O(n), você apenas não está vendo. Mas em geral ele não é considerado porque não tem relação com o objeto que estamos inspecionando que é o array. Mas tem que ter cuidado porque poderia virar O(n2) se fosse outra coisa.

Portanto para a análise do array ou contagem, todos são O(n) (considere oque o kht disse).

Curiosamente o range() e enumarate() são loops escondidos, não necessariamente relacionado ao que está sendo observado, mas estritamente falando, a complexidade total seria O(n)+O(m), em alguns casos poderia ser pior que isso. Mas essas funções são O(1) em qualquer situação, mesmo sabendo que tem um loop lá dentro. Como exercício, não vale para quem já sabe, imaginam porque ele é O(1)? Tem que conhecer bem Python para entender. Se demorar, alguém que sabe pode dar uma dica não reveladora.

Espero ter ajudado. Em geral estou à disposição na plataforma (sem abusos :D)

Farei algo que muitos pedem para aprender a programar corretamente, gratuitamente. Para saber quando, me segue nas suas plataformas preferidas. Quase não as uso, não terá infindas notificações (links aqui).