100515

A) Considere um arquivo cujos registros possuem uma chave única, utilizada para localização de registros no arquivo. Para se obter um determinado registro a partir de sua chave, percorrendo sequencialmente o arquivo com n registros na ordem em que os registros aparecem, determine a função de complexidade f para os seguintes casos:

 

Melhor caso: f(n) = ______________

 

Pior caso: f(n) = ______________

 

Caso médio: f(n) = ______________

 

B) Informe a complexidade assintótica O( f ) correspondente à sua respectiva classe algorítmica de problema:

 

Complexidade constante: f(n) = ______________

 

Complexidade logarítmica: f(n) = ______________

 

Complexidade linear: f(n) = ______________

 

Complexidade quadrática: f(n) = ______________

 

Complexidade cúbica: f(n) = ______________

 

Complexidade exponencial: f(n) = ______________