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?