Worst-case complexity of this function?
Hi,
Could you tell me why the worst-case complexity of the sort() function is O(nlg(n))?
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?
}
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:
n * lg(n) + n => O(n), because n is of higher growth order than n * lg(n)
What am I doing wrong?