complexité d'exécution pour deux algorithmes (Big O de calcul de la notation)

Question

quelle est la notation Big O pour que les deux algorithmes:

def foo1(n): 
    if n > 1: 
     for i in range(int(n)): 
      foo1(1) 
     foo1(n/2) 

def foo2(lst1, lst2): 
    i = 1 
    while i < max(len(lst1), len(lst2)): 
      j = 1 
      while j < min(len(lst1), len(lst2)): 
       j *= 2 
      i *= 2 

Je pensais que foo1 la complexité du temps d'exécution est O (n), car dans ce cas si je vois la boucle je peux le faire:

T (n) = O (n) + O (n/2) < = c * O (n) (c est const) pour tout n.

est-ce exact?

et je ne peux pas calculer le temps d'exécution de foo2 quelqu'un peut-il m'aider à le faire.

... merci

Answer 1

1. Le nombre d'opérations T(n) est égal à T(n/2) + n. En appliquant le Master theorem nous obtenons T(n) = O(n). En termes simples, il y a n + n/2 + n/4 + ... + 1 opérations qui sont inférieures à 2*n et O(n).

2. La boucle interne ne dépend pas de la boucle externe, donc nous pouvons les traiter indépendamment. T(n) = O(log(maxlen) * log(minlen)).