Thread: 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?

Originally Posted by hk_mp5kpdw

Are you sure n is of higher growth order than n*lg(n)? I think not.

Shouldn't it be:

O(1) < O(log(n)) < O(n) < O(nlog(n)) < O(n^2)... for large n's?

Or am I missing something?


And thanks for the input ILoveVectors but I already know that.