A medição da complexidade de um algoritmo é tradicionalmente feita em ciências da computação utilizando-se análise assintótica a qual utiliza o que é chamado de notação Big O (o O(n) do qual seu enunciado fala).
Um algoritmo com complexidade O(n) é nada mais que um algoritmo de tempo linear, o que significa que o tempo que ele leva para executar é um reflexo direto do tamanho da entrada de dados que ele utiliza e que esse tempo cresce de forma constante e...linear!
Em termos práticos o desejado pelo enunciado do seu problema é que se digamos seu algoritmo realize uma etapa que leve aproximadamente 1 segundo para calcular a fatorial de 1
o cálculo da fatorial de 2
deveria realizar duas etapas e levar aproxidamente 2 segundos, a fatorial de 3
realizaria três etapas e levaria aproxidamente 3 segundos, e assim sucessivamente, para cada valor acima seu tempo cresce linearmente.
Quanto a seu algoritmo atender a demanda, sim ele atende, isso pode ser confirmado vendo que cada fatorial acima de um anterior gera apenas uma chamada extra a fatorial
sendo que fatorial
realiza apenas operações de tempo constante (não vou entrar em mais detalhes aqui pois o assunto é extenso, sugiro que veja os links que usei sobre análise assintótica e Big O).