# Worst-case complexity of this function?

• 08-17-2005
Ariod
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?
• 08-17-2005
ILoveVectors
searching a linked list is O(N)
searching a already sorted binary tree is O(log N)

QuickSort/BubbleSort/Selection worst case is O(N squared)

HeapSort worst case is O(N log N)
• 08-17-2005
hk_mp5kpdw
Quote:

Originally Posted by Ariod
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?

Are you sure n is of higher growth order than n*lg(n)? I think not.
• 08-17-2005
Ariod
Quote:

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.