Worst-case complexity of this function?

This is a discussion on Worst-case complexity of this function? within the C Programming forums, part of the General Programming Boards category; Hi, Could you tell me why the worst-case complexity of the sort() function is O(nlg(n))? Code: struct s1 { long ...

  1. #1
    Registered User
    Join Date
    Aug 2003
    Posts
    34

    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?

  2. #2
    Banned
    Join Date
    Jun 2005
    Posts
    594
    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)
    Last edited by ILoveVectors; 08-17-2005 at 12:22 PM.

  3. #3
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,806
    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.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  4. #4
    Registered User
    Join Date
    Aug 2003
    Posts
    34
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 03-05-2009, 11:32 AM
  2. Bisection Method function value at root incorrect
    By mr_glass in forum C Programming
    Replies: 3
    Last Post: 11-10-2005, 09:10 AM
  3. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  4. char copy
    By variable in forum C Programming
    Replies: 8
    Last Post: 02-06-2005, 10:18 PM
  5. Xmas competitions
    By Salem in forum Contests Board
    Replies: 88
    Last Post: 01-03-2004, 02:08 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21