complexity

Discussion in 'C Programming' started by raghu, Dec 10, 2006.

  1. raghu

    raghu Guest

    How to find the complexity of a C program? Can anyone explain it with
    an example...

    Thanks a lot.
     
    raghu, Dec 10, 2006
    #1
    1. Advertising

  2. raghu

    coldsun Guest

    There is, basically, no automatic way to find the complexity of a C
    program, or program in any other language. In order to find out the
    complexity of an algorithm, you have to perform manual analysis.
    "introdcution to algorithms" and the famous TAOCP by Knuth may help you
    here.
    "raghu дµÀ£º
    "
    > How to find the complexity of a C program? Can anyone explain it with
    > an example...
    >
    > Thanks a lot.
     
    coldsun, Dec 10, 2006
    #2
    1. Advertising

  3. "raghu" <> writes:
    > How to find the complexity of a C program? Can anyone explain it with
    > an example...


    What exactly do you mean by "complexity"? The language provides no
    definition for the term.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
     
    Keith Thompson, Dec 10, 2006
    #3
  4. raghu

    Sourcerer Guest

    "Keith Thompson" <> wrote in message
    news:...
    > "raghu" <> writes:
    >> How to find the complexity of a C program? Can anyone explain it with
    >> an example...

    >
    > What exactly do you mean by "complexity"? The language provides no
    > definition for the term.


    I believe he means spatial and temporal complexity.

    You can find out what the temporal complexity of the program is if you manage to
    determine how its time of execution grows with the number of elements it needs
    to process. If the execution of the program is independent of the number of
    those elements, its temporal complexity is O(1). If it grows in linear
    proportion to the number of elements, it is O(n), etc.

    For example, if you have defined a node of the binary tree like this

    struct node {
    int a;
    struct node *less;
    struct node *more;
    };

    where less points to a node which contains int a which is smaller than in this
    node, and more points to a node where int a is larger than here, then you can
    place elements into this tree by using these constraints.

    Let's assume you've also balanced the tree. To find a particular element in this
    tree, the temporal complexity would be O(ld(n)) (dual logarythm, or logarythm of
    base 2).

    Spatial complexity is similar, only you look at this not in terms of the time
    the program needs to execute, but how much space it requires (usually stack is
    observed). If the stack is not dependent on the number of elements you need to
    process, the complexity is O(1). If it grows in proportion to the number of
    elements, the complexity is O(n), etc.

    --
    "It is easy in the world to live after the world's oppinion; it easy in solitude
    to live after our own; but the great man is he who in the midst of the crowd
    keeps with perfect sweetness the independence of solitude."
    Ralph Waldo Emerson, Self-reliance 1841
    http://pinpoint.wordpress.com/
     
    Sourcerer, Dec 10, 2006
    #4
  5. raghu

    Guest

    On Dec 10, 1:19 pm, "raghu" <> wrote:
    > How to find the complexity of a C program? Can anyone explain it with
    > an example...
    >
    > Thanks a lot.


    Well, the complexity i know is the number of distinct paths that can
    be executed in a particular function, naturally a big complexity is bad
    as it would require more number of test cases to test, more time to
    understand the flow and logic involved in a particular function, and
    this is know as Mccabe's cyclomatic complexity...
     
    , Dec 11, 2006
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. reducing complexity

    , Oct 12, 2004, in forum: ASP .Net
    Replies:
    0
    Views:
    340
  2. =?Utf-8?B?TW9yZ2FuIFJvZGVyaWNr?=

    2.0 Controlling password complexity in Membership

    =?Utf-8?B?TW9yZ2FuIFJvZGVyaWNr?=, Apr 21, 2005, in forum: ASP .Net
    Replies:
    3
    Views:
    559
    clintonG
    Apr 22, 2005
  3. Frank D. Greco
    Replies:
    0
    Views:
    345
    Frank D. Greco
    Feb 15, 2005
  4. Scott Balmos

    How much complexity to put in POJOs?

    Scott Balmos, Jul 11, 2005, in forum: Java
    Replies:
    6
    Views:
    388
    Thomas G. Marshall
    Jul 13, 2005
  5. _Hobbes

    Opinions on complexity

    _Hobbes, Dec 11, 2005, in forum: Java
    Replies:
    21
    Views:
    834
    Luc The Perverse
    Dec 17, 2005
Loading...

Share This Page