complexity of an algorithm

[junky_fellow]

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 .......

[Ben Pfaff]

ju**********@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.

[Christian Bau]

In article <8c**************************@posting.google.com >,
ju**********@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".

[Joona I Palaste]

junky_fellow <ju**********@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 (pa*****@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

[Derk Gwen]

ju**********@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.

[Malcolm]

"junky_fellow" <ju**********@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.