Obrigado a todos respondendo com ideias e soluções alternativas. Formas mais eficientes de resolver problemas são sempre bem-vindas, bem como lembretes para questionar minhas suposições. Dito isso, gostaria que você ignorasse por um momento qual problema eu estou tentando resolver com o algoritmo, e apenas me ajude a analisar a grande complexidade do meu algoritmo conforme o escrevi - todos os caminhos simples em um gráfico usando a pesquisa limitada por profundidade como descritoAquie implementadoAqui. Obrigado!

Edit: Este é o dever de casa, mas eu já enviei esta tarefa e gostaria apenas de saber se a minha resposta está correta. Eu fico um pouco confuso com a complexidade do Big-O quando a recursão está envolvida.

Pergunta original abaixo:

Eu estou tentando encontrar a complexidade de uma busca de todos os caminhos como dada poristo algoritmo. Dados dois vértices, estou encontrando todos os caminhos simples entre eles usando uma pesquisa em profundidade.

Eu sei que a complexidade de tempo do DFS é O (V + E) e sua complexidade de espaço é O (V), e minha intuição é que a complexidade de uma busca de todos os caminhos será mais do que isso, mas não consigo determinar o que será.

Perguntas SO relacionadasAqui eAqui.

Atualização (em resposta a um comentário abaixo):

Estou tentando resolver oseis graus de Kevin Bacon problema. Isso geralmente requer encontrar o menor grau de separação entre um par de atores, mas eu tenho que encontrar todos os graus de separação (por enquanto, menos de 6, mas isso pode mudar).