PAA-8-eficienciaDeAlgoritmosRecursivos-correcao

Prévia do material em texto

Profa. Thaís Alves Burity Rocha 
EFICIÊNCIA DE ALGORITMOS 
Agenda 
 Recorrências 
 Análise da eficiência do Merge Sort usando 
recorrência 
 Métodos para resolver recorrências 
 Substituições retrógadas 
 Árvore de recursão 
 Teorema mestre 
 Prova de solução de recorrência por indução 
Introdução 
 Diferentemente da análise de algoritmos iterativos, 
que utiliza somatórios para verificar a eficiência, a 
análise de algoritmos recursivos estabelece uma 
equação especial, chamada de recorrência 
 
 Uma recorrência é uma equação ou desigualdade 
que descreve uma função em termos de seu valor 
em entradas menores 
Exemplo: Fatorial 
 
 
 
 
 Qual o indicador do tamanho da entrada? 
 n 
 Qual a operação básica? 
 A multiplicação, cujo número de execuções indicaremos 
por M(n) 
Fat(n) 
se n=0, então retorne 1 
senão, retorne [n ∙ Fat(n-1)] 
Exemplo: Fatorial 
 Como é calculada de acordo com a fórmula 
 Fat(n) = Fat(n-1) ∙ n , para n>0 
 
 O número de multiplicações M(n) necessários para 
calcular Fat(n) deve satisfazer a igualdade: 
 M(n) = M(n-1) + 1 
 
 
 
 
 
 Note que M(n) é recursiva 
Para calcular as 
multiplicações em 
Fat(n-1) 
Para calcular a 
multiplicação n ∙ Fat(n-1) 
Recursão 
 Este tipo de equação é chamado de recorrência 
 
 Nosso objetivo agora é resolver a recorrência M(n) 
= M(n-1) + 1 
 Isto é, encontrar uma fórmula para M(n) somente em 
termos de n 
 
 Existem infinitas sequências que satisfazem esta 
recorrência 
Recorrências 
 Para determinar uma sequência unicamente, 
precisamos de uma condição inicial que nos diga o 
valor com o qual a sequência começa 
 
 Podemos obter este valor verificando a condição 
que faz o algoritmo parar sua chamada recursiva 
 se n=0, então retorne 1 
Recorrências 
 Isto nos mostra duas coisas: 
 Como as chamadas param quando n=0, este é o 
menor valor de n para qual o algoritmo é executado 
 
 Verificando a linha de saída do código, vemos que 
quando n=0, o algoritmo não realiza multiplicação 
 
 Então a condição de inicialização que buscamos é: 
M(0) = 0 
Recorrências 
 Temos então a recorrência e a condição inicial para 
o número de multiplicações do algoritmo M(n): 
M(n) = M(n-1) + 1 para n > 0 
M(0) = 0 
 
 Como resolver esta recorrência? 
Substituições retrógadas 
 Dentre diversas técnicas, podemos usar o método das 
substituições retrógadas 
 
 A ideia do método é a seguinte: 
M(n) = M(n-1) + 1 
 = [ M(n-2) + 1 ] + 1 = M(n-2) + 2 
 = [ M(n-3) + 1 ] + 2 = M(n-3) + 3 
 
 Após verificarmos as 3 primeiras linhas, vemos um 
padrão que torna possível predizer as próximas linhas 
 M(n) = M(n-i) + i 
Substituições retrógadas 
 Devemos então levar em conta a condição inicial dada 
 Como ela é especificada para n = 0, queremos reescrever 
a expressão usando M(0), cujo valor é conhecido 
 Logo, n-i = 0 e, portanto, i = n 
 Agora, devemos substituir i = n na fórmula padrão, para 
obter o último resultado: 
 M(n) = M(n-i) + i 
 = M(n-n) + n 
 = M(0) + n 
 = 0 + n 
 = n 
Algoritmos Recursivos 
 Muitos algoritmos recursivos seguem a estratégia de 
divisão-e-conquista 
 
 Dividir: Divide a sequência de n elementos a serem 
ordenados em duas subsequências de n/2 elementos cada 
 
 Conquistar: Ordena as duas subsequências recursivamente 
 
 Combinar: Faz a intercalação das duas sequências 
ordenadas, de modo a produzir a resposta ordenada 
 
 Observação: Nem sempre a divisão é por 2 
Exemplo: MergeSort 
 
 
 
 
 
 
 Dividir: Linha 2 
 Conquistar: Linhas 3 e 4 
 Combinar: Linha 5 
 
Maior inteiro ≤ (p+r)/2 
MergeSort: Descrição geral 
 Operação chave: Intercalação de duas sequências 
ordenadas no passo de combinação 
 
 Para executarmos a intercalação, utiliza-se o procedimento 
auxiliar Merge(A, p, q, r) 
 A é um vetor 
 p, q e r são os índices de elementos do vetor A, sendo p≤q< r 
 O procedimento pressupõe que os sub-vetores A[p...q] e 
A[q+1...r] estão ordenados 
 O procedimento intercala (mescla) esses sub-vetores para formar 
um único vetor ordenado que substitui o vetor atual A[p…r] 
Operação de Merge 
 Analogia com o jogo de cartas: 
 2 pilhas de cartas ordenadas, com a face para cima 
 As cartas de menor valor no topo 
 
 Juntar as 2 pilhas em uma pilha de saída 
ordenada, que ficará com a face para baixo, 
fazendo a intercalação 
Operação de Merge 
 O passo básico consiste em: 
 Escolher a menor dentre as cartas no topo de cada pilha 
 Removê-la de sua pilha 
 Colocá-la com a face voltada para baixo sobre a pilha de saída 
 
 Esse passo é repetido até que uma das pilhas de entrada 
se esvazie 
 A pilha de entrada que sobrou é colocada sobre a pilha de 
saída, com a face para baixo 
 
 Cada passo básico demanda um tempo constante, pois são 
verificadas apenas as duas cartas superiores 
 
Operação de Merge 
 Linhas 1-2: definem o tamanho dos sub-
vetores A[p…q] e A[q+1…r], 
respectivamente 
 
 Linha 3: cria os vetores L e R com tamanhos 
(n1+1) e (n2+1), respectivamente 
 +1 para armazenar a sentinela (sinaliza o 
fim do vetor) 
 
 Loop (linhas 4-5): copia os valores na 1a 
metade de A (A[p…q]) para o vetor L 
 
 Loop (linhas 6-7): copia os valores na 2a 
metade de A (A[q+1…r]) para o vetor R 
 
 Linhas 8-9: incluem a sentinela nos vetor L e 
R, respectivamente 
Operação de Merge: Linhas 1-9 
 Merge(A, 9, 12, 16) 
… 
8 
2 
9 
4 
10 
5 
11 
7 
12 
1 
13 
2 
14 
3 
15 
6 
16 
… 
17 
divisão 
2 
1 
4 
2 
5 
3 
7 
4 
∞ 
5 
vetor L 
(ordenado) 
1 
1 
2 
2 
3 
3 
6 
4 
∞ 
5 
vetor R 
(ordenado) 
p q q+1 r 
A 
Operação de Merge: Linhas 12-17 
… 
8 
2 
9 
4 
10 
5 
11 
7 
12 
1 
13 
2 
14 
3 
15 
6 
16 
… 
17 
A 
k 
2 
1 
4 
2 
5 
3 
7 
4 
∞ 
5 
L 
i 
1 
1 
2 
2 
3 
3 
6 
4 
∞ 
5 
R 
j 
(a) 
… 
8 
1 
9 
4 
10 
5 
11 
7 
12 
1 
13 
2 
14 
3 
15 
6 
16 
… 
17 
A 
k 
2 
1 
4 
2 
5 
3 
7 
4 
∞ 
5 
L 
i 
1 
1 
2 
2 
3 
3 
6 
4 
∞ 
5 
R 
j 
(b) 
… 
8 
1 
9 
2 
10 
5 
11 
7 
12 
1 
13 
2 
14 
3 
15 
6 
16 
… 
17 
A 
k 
2 
1 
4 
2 
5 
3 
7 
4 
∞ 
5 
L 
i 
1 
1 
2 
2 
3 
3 
6 
4 
∞ 
5 
R 
j 
(c) 
… 
8 
1 
9 
2 
10 
2 
11 
7 
12 
1 
13 
2 
14 
3 
15 
6 
16 
… 
17 
A 
k 
2 
1 
4 
2 
5 
3 
7 
4 
∞ 
5 
L 
i 
1 
1 
2 
2 
3 
3 
6 
4 
∞ 
5 
R 
j 
(d) 
Operação de Merge: Linhas 12-17 
… 
8 
1 
9 
2 
10 
2 
11 
3 
12 
1 
13 
2 
14 
3 
15 
6 
16 
… 
17 
A 
k 
2 
1 
4 
2 
5 
3 
7 
4 
∞ 
5 
L 
i 
1 
1 
2 
2 
3 
3 
6 
4 
∞ 
5 
R 
j 
(e) 
… 
8 
1 
9 
2 
10 
2 
11 
3 
12 
4 
13 
2 
14 
3 
15 
6 
16 
… 
17 
A 
k 
2 
1 
4 
2 
5 
3 
7 
4∞ 
5 
L 
i 
1 
1 
2 
2 
3 
3 
6 
4 
∞ 
5 
R 
j 
(f) 
… 
8 
1 
9 
2 
10 
2 
11 
3 
12 
4 
13 
5 
14 
3 
15 
6 
16 
… 
17 
A 
k 
2 
1 
4 
2 
5 
3 
7 
4 
∞ 
5 
L 
i 
1 
1 
2 
2 
3 
3 
6 
4 
∞ 
5 
R 
j 
(g) 
… 
8 
1 
9 
2 
10 
2 
11 
3 
12 
4 
13 
5 
14 
6 
15 
6 
16 
… 
17 
A 
k 
2 
1 
4 
2 
5 
3 
7 
4 
∞ 
5 
L 
i 
1 
1 
2 
2 
3 
3 
6 
4 
∞ 
5 
R 
j 
(g) 
Operação de Merge: Linhas 12-17 
… 
8 
1 
9 
2 
10 
2 
11 
3 
12 
4 
13 
5 
14 
6 
15 
7 
16 
… 
17 
A 
k 
2 
1 
4 
2 
5 
3 
7 
4 
∞ 
5 
L 
i 
1 
1 
2 
2 
3 
3 
6 
4 
∞ 
5 
R 
j 
(i) 
Operação de Merge: Eficiência 
 Linhas 1-3 e 8-11 
 Tempo constante 
 
 Linhas 4-7 
 Loop for: tempo O(n), dado que 
n1=n2=n/2 
 
 Linhas 12-17 
 Loop for: n iterações com tempo 
constante, assim tempo O(n) 
 
 Portanto, o algoritmo é 
executado em tempo O(n), 
onde n=r-p+1 
 
MergeSort: Visão geral 
MergeSort(A, 1, 8) 
A = {5, 2, 4, 6, 1, 3, 2, 6}, n=8 
Derivando relações de recorrências 
 Determinar o indicador n do tamanho da entrada 
 Consideramos T(n) = tempo de execução sobre um problema de 
tamanho n 
 
 Verificar que valor de n é usado como base da recursão 
 Em geral, é um valor único (n=1, por exemplo), mas pode ser 
valores múltiplos 
 Vamos considerar esse valor como n0 
 
 Determinar T(n0) 
 Pode-se usar uma constante c, mas, em muitos casos, um número 
específico é necessário 
 T(n) = c → O(1) , se n = n0 
Derivando relações de recorrências 
 Supondo que o problema seja dividido em a 
subproblemas, cada um dos quais com tamanho 
n/b, onde n é o tamanho do problema original 
 No MergeSort, temos a=b=2 
 
 Se levarmos em conta o tempo D(n) para dividir o 
problema em subproblemas e o tempo C(n) para 
combinar as soluções dadas aos subproblemas, 
obteremos a recorrência... 
 T(n) = a∙T(n/b) + D(n) + C(n) 
Derivando relações de recorrências 
 Resumo 
 
 T(n) = c → O(1) , se n = n0 
 
 T(n) = a∙T(n/b) + D(n) + C(n), caso contrário 
Exemplo: MergeSort 
Análise de algoritmos 
 O indicador do tamanho do problema é n=r-p+1 
 Isto é, o tamanho do vetor que devemos ordenar 
 
 O tempo para ordenação quando n=0 (nenhum elemento) 
ou n=1 (p=r) é constante, pois o vetor já está ordenado 
 
 Quando n>1, para achar T(n), vamos dividir em algumas 
etapas... 
Exemplo: MergeSort 
 Etapa dividir: Para dividir, o algoritmo simplesmente calcula o 
índice médio do vetor, o que demora um tempo constante 
 D(n) = O(1) 
 
 Etapa conquistar: Resolvemos recursivamente dois 
subproblemas (a=2). Cada um tem tamanho n/2 (b=2) e assim 
contribui com tempo de execução: 
 2 ∙ T(n/2) 
Exemplo: MergeSort 
 Combinar: Já vimos que o procedimento Merge em um vetor 
de n elementos leva o tempo O(n), assim: 
 C(n) = O(n) 
 
 Se somarmos os tempos das funções D(n) e C(n) teremos: 
 O(1) + O(n) = O(n) 
 
 A adição desta função ao termo 2∙T(n/2) da etapa de 
conquista fornece a recorrência para o tempo de execução do 
pior caso T(n) 
 Relação de recorrência 
 
 
 Vamos reescrever a recorrência para resolvê-la de 
forma intuitiva 
 
 
 
 Onde a constante c representa 
 O tempo para resolver problemas de tamanho 1 
 E também o tempo por elemento do vetor para as etapas de 
dividir e combinar 
 
Pior caso para o MergeSort 
Árvore de recursão 
 Vamos admitir que n é uma potência exata de 2 
 Vamos expandir T(n) em uma árvore representando 
a recorrência 
 cn é a raiz (custo do nível superior da recursão) e 
T(n/2) são as duas recorrências menores 
(a) (b) 
(c) 
Árvore de recursão 
 Continuamos a expandir cada nó na árvore 
 O custo para cada um dos dois sub-nós no segundo 
nível de recursão é c(n/2) 
Árvore de recursão 
 Continuamos a 
expandir cada 
nó na árvore 
até os 
tamanhos de 
problemas se 
reduzirem a 1, 
cada qual com 
o custo c 
Resolvendo recorrência: MergeSort 
 T(n) é o somatório do custo de todos os níveis da 
árvore de recursão 
 Já se sabe que o custo de cada nível é cn 
 Agora vamos calcular o total de níveis 
 O tamanho dos subproblemas no nível i é n/2i 
 No último nível, os subproblemas possuem tamanho 1 
 Se acharmos o nível i para o qual os subproblemas tem tamanho 
1, achamos o total de níveis! 
 n/2i = 1 
 n = 2i 
 i = log2n 
 Como os níveis são contados a partir de 0, o total de níveis é 
log2n + 1 
Resolvendo recorrência: MergeSort 
 Dado que o número de níveis na árvore de 
recursão é lg n+1 e que cada nível tem custo cn, 
concluímos que, no pior caso 
 T(n) = cn × ( lg n+1) → Θ(n lg n) 
 
 Muito melhor que o Bubblesort ou InsertSort, que 
possuem complexidade Θ(n2), no pior caso 
Árvore de recursão: Resumo 
 Passo 1: Traçar a árvore de recursão 
 Lembre que cada nó representa o custo de um único 
subproblema em algum lugar no conjunto de invocações de 
funções recursivas 
 Passo 2: Somamos os custos dentro de cada nível da 
árvore 
 Cuidado: Nem sempre os níveis tem o mesmo custo! 
 Passo 3: Somamos os custos dos níveis 
 
 
 k é o último nível na árvore de recursão 
 ci é o custo do nível i 
Recorrências: Fórmulas gerais 
Θ(n) 
 
Θ(n lgn + n) 
 
Θ(lg lg n) 
 
 
Θ(n lg n) 
 Fornece uma “receita de bolo” para resolver 
recorrências da forma: 
 T(n) = a T(n/b) + f(n) 
 Onde: a>= 1 e b>1 são constantes e f(n) é uma função 
assintoticamente positiva 
 
 Trata de recorrência que descreve o tempo de 
execução de um algoritmo que divide um problema 
de tamanho n em a subproblemas de tamanho n/b 
 O custo de dividir o problema e combinar os resultados é 
descrito por f(n) 
Método mestre 
 Casos: 
 Se f(n) = O(nlogba- ε), para algum ε > 0, então 
 T(n) = Θ(nlogba) 
 
 Se f(n) = Θ(nlogba), então 
 T(n) = Θ(nlogba ∙ lg n) 
 
 Se f(n) = Ω(nlogba+ ε), para algum ε > 0, e se 
a∙f(n/b)≤c ∙f(n) para algum 0< c < 1 e n 
suficientemente grande, então 
 T(n) = Θ(f(n)) 
Método mestre 
Método mestre: Significado 
 Em cada um dos três casos, a função f(n) é 
comparada com a função nlogba e a solução de T(n) é 
determinada pela maior das duas funções 
 No caso 1, f(n) tem de ser polinomialmente menor que 
nlogba, ou seja, menor por um fator nε 
 No caso 2, se as duas funções são assintoticamente iguais, 
T(n) = Θ(nlogba × lg n) 
 No caso 3, f(n) tem de ser polinomialmente maior do que 
nlogba , ou seja, maior por um fator nε e, além disso, 
satisfazer a condição de que a∙f(n/b) ≤ c∙f(n) 
 MergeSort: 
 T(n) = 2∙T(n/2) + n 
 a = b = 2 
 f(n) = n 
 log22 = 1 
 Logo, g(n) = nlogba = n, o que significa que f(n)=g(n) 
 Cai no caso 2 
 
 Resultado: T(n) = Θ(nlogba ∙ lg n) = Θ(n∙lg n) 
Método mestre: Exemplos 
Método mestre: Exemplos 
 T(n) = 9∙T(n/3) + n 
 a = 9 e b = 3 
 f(n) = n 
 logba = log39 = 2 
 Logo, g(n) = nlogba = n2 
 Daí, temos que f(n) é menor que g(n) por um fator de n 
=n1=nε 
 Cai no caso 1 
 
 Resultado: T(n) = Θ(nlogba) = Θ(n2) 
Método mestre: Exemplos 
 T(n) = 3 T(n/4) + n∙lg n 
 a= 3 e b = 4 
 f(n) = n lg n 
 logba = log43 ≈ 0,8 => g(n) = n
logba= n0,8 
 f(n)/g(n) = n0,2lg n 
 Logo, f(n) é maior que g(n) por um fator nε, sendo ε = 0,2 
 Agora, basta mostrar que a∙f(n/b)≤c∙f(n), para c> 0 e n 
suficientemente grande, para provar que o caso 3 se aplica 
 3 (n/4) lg(n/4) ≤ (3/4) n lg n, escolhendo c=3/4 
 
 Resultado: T(n) = Θ(f(n)) = Θ(n lg n) 
 
 Os 3 casos não abrangem todas as possibilidades para 
f(n) 
 Quando f(n) é menor que nlogba, mas não é polinomialmente 
menor 
 Quando f(n) é maior que nlogba, mas não é polinomialmente 
maior ou a condição a∙f(n/b) ≤ c∙f(n) não é satisfeita 
 
 Uma função P é denominada polinômio se 
 
 
 n é um número inteiro não negativo 
 os números a0, a1, ..., an-1, an são constantes, chamadas de 
coeficientes do polinômio 
 O valor do maior expoente de x é o grau da função 
 
Método mestre: Casos não cobertos 
Método mestre: Exemplos 
 T(n) = 2 T(n/2) + n lg n 
 a=2, b=2, f(n) = nlgn 
 nlogba= nlog22 = n 
 
 O caso 3 não se aplica 
 Embora f(n) = n lg n seja assintoticamente maior do 
que n, ela não é polinomialmente maior 
 f(n)/ nlogba = (n lg n)/n = lg n 
 Não é possível dizer que f(n) é maior que g(n) por um fator 
nε, sendo ε>0 
Exercício 1 
 Aplique o método mestre na recorrência 
 T(n) = 2 T(n/2) + 10n 
 
Exercício 1: Solução 
 T(n) = 2 T(n/2) + 10n 
 a= 2 e b = 2 
 f(n) = 10n 
 logba = log22=1 => g(n) = n
logab = n 
 Dado que na análise assintótica podemos desprezar as 
constantes, f(n) = g(n) 
 Cai no caso 2 
 T(n) = Θ(nlogba ∙ lg n) = Θ(n∙lg n) 
 
Exercício 2 
 Aplique o método mestre na recorrência 
 T(n) = 8 T(n/2) + 1000n2 
Exercício 2: Solução 
 T(n) = 8 T(n/2) + 1000n2 
 a= 8 e b = 2 
 f(n) = 1000n2 
 logba = log28=3 => g(n) = n
logab = n3 
 f(n) é inferior a g(n) por um fator nε, sendo ε = 1 
 Cai no caso 1 
 T(n) = Θ(nlogba) = Θ(n3) 
 
Exercício 3 
 Analise a complexidade da busca binária recursiva 
bs(A, inicio, fim, chave) 
 meio = (inicio+fim)/2 
 se (inicio > fim) então 
 retorne NULL 
 se (chave = A[meio]) então 
 retorne meio 
 se (chave < A[meio]) então 
 retorne bs(A,inicio, meio-1, chave) 
 senão 
 retorne bs(A,meio+1,fim, chave) 
 
Exercício 3: Solução 
 n = tamanho de A = fim – inicio + 1 
 Condição de parada da recursividade: 
 inicio > fim, ou seja, quando n = 0 
 fim – inicio + 1 = 0 
 inicio = fim + 1 
 fim+1 > fim !!!! 
 chave == A[meio] 
 Quando A está vazio (n=0), o algoritmo retorna null 
 Caso contrário, o algoritmo divide A em 2 partes, cada uma 
de tamanho n/2 
 Se a chave estiver em A[meio], o algoritmo retorna meio 
 Se não, o algoritmo vai procurar a chave em uma das duas 
partes em que A foi dividido 
 
Exercício 3: Solução 
 
 
 
 
 
 
 
 Ou seja, ao contrário do MergeSort, o tamanho da 
entrada do algoritmo vai diminuindo a cada iteração 
A[2] A[1] A[3] A[4] A[5] A[6] A[7] A[8] 
A[2] A[1] A[3] A[4] A[5] A[6] A[7] A[8] 
chave < A[4] chave > A[4] 
A[2] A[1] A[3] A[4] A[5] A[6] A[7] A[8] 
Exercício 3: Solução 
 
1 
1 
1 
1 
1 
 
T(n/2) 
 
T(n/2) 
bs(A, inicio, fim, chave) 
 meio = (inicio+fim)/2 
 se (inicio > fim) então 
 retorne NULL 
 se (chave = A[meio]) então 
 retorne meio 
 se (chave < A[meio]) então 
 retorne bs(A,inicio, meio-1, chave) 
 senão 
 retorne bs(A,meio+1,fim, chave) 
 
Exercício 3: Solução 
 Se n=0, tempo constante = 1 
 Se A[meio] = chave, tempo constante = 3 
 Calcular meio: 1 
 Comparar chave: 1 
 Retornar meio: 1 
 Senão, T(n/2) + 3 
 Calcular meio: 1 
 Comparar chave: 1 
 Retornar posicao da chave: 1 
 
Exercício 3: Solução 
 Recorrência: 
 T(n) = 3, se n<2 
 T(n) = T(n/2) + 3, caso contrário 
 Solução da recorrência pelo Método Mestre 
 a = 1 e b = 2 
 logba = log21 = 0 => g(n) = n
0 = 1 
 f(n) = 3 
 f(n) e g(n) são constantes => f(n) = g(n) 
 Cai no caso 2 
 T(n) = Θ(nlogba ∙ lg n) = Θ(lg n) 
 
Recorrência: Prova por indução 
 T(1) = 1 
 T(n) = 2T(n/2) + n, para n>1 
 Queremos provar que T(n) = n + n lg n 
Recorrência: Prova por indução 
 T(1) = 1 
 T(n) = 2T(n/2) + n, para n>1 
 Queremos provar que T(n) = n + n lg n 
 Caso base: 
 T(2) = 2 T(2/2) + 2 = 2 × 1 + 2 = 4 
 T(2) = 2 + 2 × lg(2) = 4 
Recorrência: Prova por indução 
 T(1) = 1 
 T(n) = 2T(n/2) + n, para n>1 
 Queremos provar que T(n) = n + n lg n 
 Caso base: 
 T(2) = 2 T(2/2) + 2 = 2 × 1 + 2 = 4 
 T(2) = 2 + 2 × lg(2) = 4 
 Hipótese: Válido para valores até n-1 
 Prova 
 T(n) = 2 × (n/2 + n/2 lg(n/2)) + n 
 T(n) = n + n lg (n/2) + n 
 T(n) = n + n (lg n - lg2) + n 
 T(n) = n + n (lg n -1) + n 
 T(n) = n + n lg n - n + n 
 T(n) = n + n lg n