aber analisar uma recorrência a partir da descrição de um dado problema, é importante para a correta avaliação da complexidade do algoritmo que ser...

aber analisar uma recorrência a partir da descrição de um dado problema, é importante para a correta avaliação da complexidade do algoritmo que será projetado. E o entendimento de como cada subproblema é expandido deve ser parte integrante dessa análise. Considere um algoritmo recursivo que, dada uma entrada de tamanho n, divide a entrada em 2 (dois) subproblemas de tamanho n/2, resolve cada um recursivamente e, por fim, combina as duas partes em um tempo O(n). Em relação ao comportamento recursivo e ao limite assintótico desse algoritmo, analise as afirmativas a seguir (o tempo de execução do algoritmo para uma entrada de tamanho n será denotado por T(n)). I. A árvore de recursão gerada pelo algoritmo terá tamanho log2(n). II. Cada nível k da árvore de recursão é composto por 2k subproblemas. III. O algoritmo tem complexidade da ordem de O(nlog2) IV. A recursão pode ser descrita pela função T(n) = T(2n) + n.