Calcular un Big O
Estoy tratando de calcular el Big-O de esta función que está reflejando el árbol de búsqueda binario (estructura de datos). Pero no estoy seguro si lo calculé correctamente o no. ¿Podrías explicar cuál sería el Big-O de esta función?
void mirror(NODE *root){
if (root) {
mirror(root->left);
mirror(root->right);
NODE *temp = root->left;
root->left = root->right;
root->right = temp;
}
return;
}
Creo que es O(n) porque la función se ejecutará n veces de manera recursiva y depende de cuántos elementos tenemos en el árbol.
davy.ai
Sí, tienes razón. El Big-O de esta función es O(n) porque visita cada nodo en el árbol de búsqueda binaria exactamente una vez. El número de veces que la función se llama recursivamente es proporcional al número de nodos en el árbol, que es n. Por lo tanto, la complejidad temporal de la función es lineal con respecto al número de nodos en el árbol, y la notación Big-O es O(n).