Thread: Algorithm Complexity

  1. #1
    Logic Programmer logicwonder's Avatar
    Join Date
    Nov 2005
    Location
    Kerala, India
    Posts
    52

    Algorithm Complexity

    I have been going through sorting and searching algorithms and their implimentations in C language.

    I found two terms Time complexity & Space complexity. But most of the sorting and searching algorithms speaks more about time complexity.

    Those algorithms use lot of variables (space) and mentioning nothing about the space complexity.

    Is space complexity NOT a factor to consider in sorting and searching algorithms???

    What are your views??
    L GIK wins!!!
    Salutes from logicwonder
    Enjoy programming

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    It depends on what you're sorting, and how much you're sorting. But look at it this way: QuickSort is an inplace sort - all extra space you use comes from the stack of the recursive calls. Its space complexity is therefore O(log n), with a very low constant. MergeSort is usually done using a scratch buffer. Its space complexity is O(n), with a somewhat larger O.
    In both cases, the time complexity is O(n log n). That's more.

    In addition, memory is cheap, but time often is not. Another point is that once the sorting is done, the used memory is freed. You'll never regain the used time.

    Only systems that handle more data than fits into RAM, like databases, consider space complexity. But that's only because to those systems, space complexity IS time complexity, because it takes so long to write and read external storage.
    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

  3. #3
    Logic Programmer logicwonder's Avatar
    Join Date
    Nov 2005
    Location
    Kerala, India
    Posts
    52
    Does that mean I dont need to bother about space complexity while implimenting sorting and searching algorithms as C programs?

    Thanks CornedBee
    L GIK wins!!!
    Salutes from logicwonder
    Enjoy programming

  4. #4
    Rabble Rouser Slacker's Avatar
    Join Date
    Dec 2005
    Posts
    116
    >Does that mean I dont need to bother about space complexity
    Unless you're trying to invent a sorting algorithm, space complexity is just a matter of the needs of your program and picking the right algorithm to fit the job. For example, sometimes you can get away with bubble sort, but other times you need something with better time complexity. Usually stability is the deciding factor in choosing mergesort, even though it has an undesirable space complexity. It all depends on what you're doing. Space complexity plays a bigger part in searching because the speed of searching can vary greatly depending on how you store the data. Once again, how much it matters is up to your needs.

  5. #5
    Logic Programmer logicwonder's Avatar
    Join Date
    Nov 2005
    Location
    Kerala, India
    Posts
    52
    Thanks Slacker.
    L GIK wins!!!
    Salutes from logicwonder
    Enjoy programming

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Algorithm - Complexity.
    By visitant... in forum C Programming
    Replies: 5
    Last Post: 05-13-2003, 02:24 AM