complexity of an algorithm

Discussion in 'C Programming' started by junky_fellow, Feb 20, 2004.

  1. junky_fellow

    junky_fellow Guest

    How do we calculate the complexity of an algorithm?

    Am i right if i say the complexity of an algorithm
    is the number of comparisons done in that algorithm?

    thanx in advance .......
    junky_fellow, Feb 20, 2004
    #1
    1. Advertising

  2. junky_fellow

    Ben Pfaff Guest

    (junky_fellow) writes:

    > How do we calculate the complexity of an algorithm?
    >
    > Am i right if i say the complexity of an algorithm
    > is the number of comparisons done in that algorithm?


    Your question is outside the domain of comp.lang.c, which discusses
    only the standard C programming language, including the standard C
    library. This is a remarkably narrow topic compared to what many
    people expect.

    For your convenience, the list below contains topics that are not
    on-topic for comp.lang.c, and suggests newsgroups for you to explore
    if you have questions about these topics. Please do observe proper
    netiquette before posting to any of these newsgroups. In particular,
    you should read the group's charter and FAQ, if any (FAQs are
    available from www.faqs.org and other sources). If those fail to
    answer your question then you should browse through at least two weeks
    of recent articles to make sure that your question has not already
    been answered.

    * OS-specific questions, such as how to clear the screen,
    access the network, list the files in a directory, or read
    "piped" output from a subprocess. These questions should be
    directed to OS-specific newsgroups, such as
    comp.os.ms-windows.programmer.misc, comp.unix.programmer, or
    comp.os.linux.development.apps.

    * Compiler-specific questions, such as installation issues and
    locations of header files. Ask about these in
    compiler-specific newsgroups, such as gnu.gcc.help or
    comp.os.ms-windows.programmer.misc. Questions about writing
    compilers are appropriate in comp.compilers.

    * Processor-specific questions, such as questions about
    assembly and machine code. x86 questions are appropriate in
    comp.lang.asm.x86, embedded system processor questions may
    be appropriate in comp.arch.embedded.

    * ABI-specific questions, such as how to interface assembly
    code to C. These questions are both processor- and
    OS-specific and should typically be asked in OS-specific
    newsgroups.

    * Algorithms, except questions about C implementations of
    algorithms. "How do I implement algorithm X in C?" is not a
    question about a C implementation of an algorithm, it is a
    request for source code. Newsgroups comp.programming and
    comp.theory may be appropriate.

    * Making C interoperate with other languages. C has no
    facilities for such interoperation. These questions should
    be directed to system- or compiler-specific newsgroups. C++
    has features for interoperating with C, so consider
    comp.lang.c++ for such questions.

    * The C standard, as opposed to standard C. Questions about
    the C standard are best asked in comp.std.c.

    * C++. Please do not post or cross-post questions about C++
    to comp.lang.c. Ask C++ questions in C++ newsgroups, such
    as comp.lang.c++ or comp.lang.c++.moderated.

    * Test posts. Please test in a newsgroup meant for testing,
    such as alt.test.

    news.groups.questions is a good place to ask about the appropriate
    newsgroup for a given topic.
    Ben Pfaff, Feb 20, 2004
    #2
    1. Advertising

  3. In article <>,
    (junky_fellow) wrote:

    > How do we calculate the complexity of an algorithm?
    >
    > Am i right if i say the complexity of an algorithm
    > is the number of comparisons done in that algorithm?


    Function f () calculates the sum of 1/x for x = 1 to 1e12 without any
    comparisons:

    double f1 (double x) { return 1/x + 1/(x+1) + 1/(x+2) ... + 1/(x+9); }
    double f2 (double x) { return f1(x) + f1(x+10) + f1(x+20)...+ f1(x+90); }
    double f3 (double x) { return f2(x) + f2(x+100)...+f2 (x+900); }
    ....
    double f12(double x) { return f11(x) + f11(x+1e11) + ... + f11(x+9e11); }

    double f (void) { return f12 (1.0); }

    So the answer to your question seems to be "no".
    Christian Bau, Feb 20, 2004
    #3
  4. junky_fellow <> scribbled the following:
    > How do we calculate the complexity of an algorithm?


    > Am i right if i say the complexity of an algorithm
    > is the number of comparisons done in that algorithm?


    > thanx in advance .......


    This has pretty much nothing to do with any specific programming
    language. However, the answer to your question above is "no".
    Consider these functions:

    int isOneSmallerThanTwo(void) {
    if (1<2) return 1; else return 0;
    }

    int isOneSmallerThanTwo2(void) {
    if (1<2) if (1<2) return 1; else return 0; else if (1<2) return 1;
    else return 0;
    }

    Both are of complexity O(1), but still the latter performs one more
    comparison than the former.

    A more correct statement would be:
    "A single atomic operation or a comparison takes O(1) time. A sequence
    of such statements takes as much time as its longest operation. A loop
    iterating over such statements takes the time of the operations take,
    multiplied by the time that iterating over the loop takes."
    This statement is not perfect - there may be loopholes.

    --
    /-- Joona Palaste () ------------- Finland --------\
    \-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
    "Show me a good mouser and I'll show you a cat with bad breath."
    - Garfield
    Joona I Palaste, Feb 20, 2004
    #4
  5. junky_fellow

    Derk Gwen Guest

    (junky_fellow) wrote:
    # How do we calculate the complexity of an algorithm?
    #
    # Am i right if i say the complexity of an algorithm
    # is the number of comparisons done in that algorithm?

    Peruse a copy of Knuth's Art of Programming. Volume 1 introduces the
    topic, and he does space and time complexities throughout. It's too
    complex a topic to try to teach in one post.

    --
    Derk Gwen http://derkgwen.250free.com/html/index.html
    I have no respect for people with no shopping agenda.
    Derk Gwen, Feb 20, 2004
    #5
  6. junky_fellow

    Malcolm Guest

    "junky_fellow" <> wrote in message
    >
    > How do we calculate the complexity of an algorithm?
    >
    > Am i right if i say the complexity of an algorithm
    > is the number of comparisons done in that algorithm?
    >

    This is probably as good a measure as any - count the for, while and ifs in
    the code. switch() presents you with a bit of a problem, as do function
    pointers.

    The problem is that what you really want to know is, psychologically, how
    hard is the algorithm to implement? There isn't really a good way of
    defining this.
    Malcolm, Feb 21, 2004
    #6
  7. junky_fellow

    shlinlin

    Joined:
    Nov 20, 2010
    Messages:
    1
    max flow

    in book "introduction of Algorithm" 3rd Ed. chapter 26-Maximum Flow, exercises 26.2-10, Show how to find a maximum flow in a network G=(V,E) by a sequence of at most |E| augmenting paths. (Hint: Determine the paths after finding the maximum flow),
    except repeat copy Ford-Fulkerson and Edmonds-Karp algorithm, I do not know what else I should reply. Am I right? looking to hear advancer's advice,
    Eric, shlinlin at 37 dot com
    shlinlin, Nov 20, 2010
    #7
    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:
    334
  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:
    541
    clintonG
    Apr 22, 2005
  3. Ahmed Moustafa
    Replies:
    0
    Views:
    767
    Ahmed Moustafa
    Nov 15, 2003
  4. Bapaiah Katepalli
    Replies:
    1
    Views:
    1,483
    Mike Treseler
    Jun 23, 2006
  5. David Hláèik

    [OT] stable algorithm with complexity O(n)

    David Hláèik, Dec 13, 2008, in forum: Python
    Replies:
    27
    Views:
    774
    Dan Upton
    Dec 22, 2008
Loading...

Share This Page