Hola a todos !!!!!
Tenía na duda acerca de la compejididad que tiene algunas funciones de los ABB , necesito estudiar su complejidad computacional .
La inserción en ABB es \( O(logn) \) (logarítmica ) en el mejor caso , en cuanto al peor caso \( O(n) \) (lineal ) . Tengo la duda de si en cuanto vamos a estudiar la complejitud computacional , cúal sería las cotas adecuadas para el caso de inserción .
Por otro lado tengo la duda de si en este caso deba usar \( O(nlogn) \) dado que cada inserción se cuenta .
Dado un n que es la longitud de un vector aleatorio , su tiempo de ejecución ( insertar valor del vector n en arbol ) en nano-segundos es \( t(n) \) , para calcular la cota subestimada sería \( t(n)/log(n) \) , la ajustada \( t(n)/2*log(n) \) y la sobreestimada \( t(n)/n \) . Los resultados de con varias longitudes de n , son todos valores que va en aumento cuando n aumenta . Nose si está bien si todas los valores tienen que aumentar , lo digo porque en un ejemplo de clase la última columna la cota sobreestimada a medida que la n aumentaba la cota disminuía . Lo que no entiendo es por qué si el peor caso es lineal , los numeros tiende a bajar . Podrían recomendarme algunas cotas que deba usar . La cota ajustada tiene que tender a un valor estable .
Muchas gracias
