- **C Programming**
(*http://www.velocityreviews.com/forums/f42-c-programming.html*)

- - **complexity of an algorithm**
(*http://www.velocityreviews.com/forums/t317437-complexity-of-an-algorithm.html*)

complexity of an algorithmHow 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 ....... |

Re: complexity of an algorithmjunky_fellow@yahoo.co.in (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. |

Re: complexity of an algorithmIn article <8c7d4a6e.0402192209.728d1bfe@posting.google.com >,
junky_fellow@yahoo.co.in (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". |

Re: complexity of an algorithmjunky_fellow <junky_fellow@yahoo.co.in> 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 (palaste@cc.helsinki.fi) ------------- Finland --------\ \-- http://www.helsinki.fi/~palaste --------------------- rules! --------/ "Show me a good mouser and I'll show you a cat with bad breath." - Garfield |

Re: complexity of an algorithmjunky_fellow@yahoo.co.in (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. |

Re: complexity of an algorithm"junky_fellow" <junky_fellow@yahoo.co.in> 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. |

max flowin 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 |

All times are GMT. The time now is 08:06 AM. |

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.