Thread: Algorithm - Complexity.

  1. #1
    visitant...
    Guest

    Algorithm - Complexity.

    Hello, I'm reading a little bit about complexity in a book about algorithms. The book says that the complexity of the algorithm is calculated by the number of operations that we do in the algorithm. Example:
    Code:
    void swap(int *x, int *y)
    {
        int tmp = *x;
        
        *x = *y;
        *y = tmp;
    }
    We do here 3 steps(operations) to swap the values, but he still says that the algorithm is O(1) and not O(3). Why is O(1) if we still make 3 steps to get the result?

  2. #2
    Registered User zdude's Avatar
    Join Date
    Sep 2002
    Posts
    32
    No idea.

    I don't think there really is a way to rate algorithmic complexity.

    In ASM that would be more commands, and in machine code even more.
    Those who live by the sword get shot by those who don't.

    I can C.

    Compiler: gcc

  3. #3
    Registered User Draco's Avatar
    Join Date
    Apr 2002
    Posts
    463
    I think you may be confused with what your book is telling you. I have a book that talks a little about algorithm complexity (yes, a way to rate it does exist zdude, google it). In my book, a linear algorithm like the one you posted has a complexity of O(n) where n is the number of data items that the algorithm will be applied to, not the number of code lines in the algorithm.

  4. #4
    Registered User
    Join Date
    Oct 2002
    Posts
    27
    when talking about algorithm complexity, you usually do not bother multiplying the complexity by constants.

    That program is O(1) because it takes a constant amount of time to do the calculation.

    An algorithm is O(n) if the size of the input can vary and the time it takes to complete the algorithm is linear in respect to the size of the input.

    say you have this code where n is the size of the list

    Code:
    int main(n, list){
       int x = 0;
       int p = 0;
    
       for (i = 0; i <= n; i++){
          list(i) = p;
          x = x + p;
       }
    }
    this function runs n times and does 2 operations per time.
    so the run time is 2n, but in big O notation you don't need to mention the constant 2, only the order of growth. So it is O(n).

  5. #5
    visitant...
    Guest
    I'm starting to understand a little bit, I found some rules in my book like:
    Code:
    O(ConstantNumber) = O(1);
    O(n*(ConstantNumber)) = (ConstantNumber) * O(n) = O(n);
    With this in mind is easier to understand the problem. thanks for the help.

  6. #6
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    The big-O notation O(n) is basically defined as a constant multiplied by n: A * n.

    If you have O(3), that is 3 * A * 1.
    3 * A is another constant B, so the expression is B * 1 which is O(1).
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

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. Algorithm Complexity
    By logicwonder in forum C Programming
    Replies: 4
    Last Post: 01-09-2006, 06:03 AM
  3. 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
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM