Hi,
Could you tell me why the worst-case complexity of the sort() function is O(nlg(n))?
This function is supposed to sort a linked list using a binary search tree. It is an example from one of my school books. Here's how I calculated the worst-case complexity:Code:struct s1 { long code; struct s1 *next; }; struct s2 { long code; struct s2 *left; struct s2 *right; }; typedef struct s1 record; typedef struct s2 node; ... void sort(record **head) { record *p; node *root = NULL; long t; if (*head == NULL) { return; } p = *head; do { add(&root, p->code); // Worst-case complexity O(lg(n)) p = p->next; } while (p != NULL); // Will run n times (there are n elements in the list) p = *head; inOrder(add, &p); // Adds values to the list in sorted order. Complexity of in-order transversal is O(n), right? }
n * lg(n) + n => O(n), because n is of higher growth order than n * lg(n)
What am I doing wrong?