Complexidade de tempo de algoritmos recursivos com ramificações de diferentes complexidades - big-o, complexidade de tempo

Eu tenho o algoritmo

def alg(a):
if a == 0:
return 1
elif a % 2 == 1:
return alg(a - 1)
else:
return alg(a / 2)

e não tenho certeza de qual é a sua complexidade. Um ramo tem complexidade de O (N) e o outro O (log (N)).

Você neste caso diz que o algoritmo tem complexidade de O (N) já que é o pior caso ou a complexidade é algo completamente diferente neste caso?

Respostas:

Você normalmente encolhia os ombros e dizia "Sim, esse ramo tem O (x), e assim é pelo menos tão ruim assim".

Mas se formos um pouco espertos, podemos ver que seu algoritmo tem um caso base que é O (1) e depois dois outros casos: par e ímpar.

Se ainda, o tamanho do problema é cortado pela metade.

Se for estranho, o tamanho do problema é diminuído em 1 antes de ser cortado ao meio (como resultado de ser decrementado por 1).

O pior cenário possível é que, após cada número par cortado ao meio, seja um número ímpar, mas isso ainda é muito bom, já que isso reduz O(log(n)).