big O notation question

This is a discussion on big O notation question within the C++ Programming forums, part of the General Programming Boards category; Hello, Been wondering what is the time complexity of algorithm if we erase all elements in a linked list? Also ...

  1. #1
    l2u
    l2u is offline
    Registered User
    Join Date
    May 2006
    Posts
    630

    big O notation question

    Hello,

    Been wondering what is the time complexity of algorithm if we erase all elements in a linked list?

    Also what is the big O notation (complexity) difference betwen erasing element in a single and doubly linked list?

    How can we calculate that?

    Thanks in advance!

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    The complexity of the algorithm depends on what algorithm you use.

    There should not be a complexity difference between erasing element in a single and a doubly linked list, since erasing an element in a singly-linked list is two operations, which is O(1), and erasing an element in a doubly-linked list is three operations, which is O(1). (I'm not counting "finding the element to be deleted" as part of this, but that's identical in both cases anyway.)

  3. #3
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Actually, to remove an item from a single linked list, you will have to find the *previous* item as well, to update its pointer. The complexity of this is O(n). So deleting something is O(n) in a single linked list, and O(1) in a doubly linked list.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    Quote Originally Posted by EVOEx
    Actually, to remove an item from a single linked list, you will have to find the *previous* item as well, to update it's pointer. The complexity of this is O(n). So deleting something is O(n) in a single linked list, and O(1) in a doubly linked list.
    Clearly, erasing the next node in a singly linked list is in O(1)

    Of course, once we consider "finding the element to be deleted", in all cases erasing an arbitrary node from a linked list is in O(n).
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Quote Originally Posted by EVOEx View Post
    Actually, to remove an item from a single linked list, you will have to find the *previous* item as well, to update its pointer. The complexity of this is O(n). So deleting something is O(n) in a single linked list, and O(1) in a doubly linked list.
    Ah but there are ways around that to make it O(1) again. You simply copy the next item over the current item and then free the next item instead. You also keep a sentinel node after the end of the list to make it possible to delete the last node.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Quote Originally Posted by iMalc View Post
    Ah but there are ways around that to make it O(1) again. You simply copy the next item over the current item and then free the next item instead.
    But that comes with a different price. You lose iterator stability. One of the nice things about linked lists is that a pointer to an element stays valid no matter how you manipulate the list, as long as you don't erase that specific element.

    But with your variant of erase, you also invalidate pointers to the next element.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Oh certainly. I would never consider using such a technique, it was just an FYI I suppose.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,230
    Quote Originally Posted by l2u View Post
    Been wondering what is the time complexity of algorithm if we erase all elements in a linked list?
    The question requires a more specific context to answer. Do the elements of the list require destruction? If not, the complexity is O(1) because you can simply forget the list. This leaks memory, but you haven't specified whether that's acceptable or not. The point is, big-O discussions are usually theoretical, and theoretically, we could have a machine with infinite memory and so forgetting the list is an acceptable solution.

    On a realistic system you are going to have to at least delete the memory of each node, which requires visiting each node, and this is O(n). If you have to destruct the nodes, again, you have to visit each of them and it is O(n).
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. another do while question
    By kbpsu in forum C++ Programming
    Replies: 3
    Last Post: 03-23-2009, 12:14 PM
  2. Replies: 5
    Last Post: 02-20-2004, 08:36 AM
  3. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  4. opengl DC question
    By SAMSAM in forum Game Programming
    Replies: 6
    Last Post: 02-26-2003, 08:22 PM
  5. Big O Notation
    By Drew in forum C++ Programming
    Replies: 1
    Last Post: 09-30-2001, 01:22 AM

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