Complexity of data structure

C

C learner

Why calculation of complexity of various algorithms(Linear search,
bubble sort) confined to number of comparisons, whereas the arithmetic
operations and other operations are not considered, though these also
may eat significant processing power.
 
I

Ian Collins

Why calculation of complexity of various algorithms(Linear search,
bubble sort) confined to number of comparisons, whereas the arithmetic
operations and other operations are not considered, though these also
may eat significant processing power.

Because the arithmetic operations are common to all algorithms.
 
E

Eric Sosman

Why calculation of complexity of various algorithms(Linear search,
bubble sort) confined to number of comparisons, whereas the arithmetic
operations and other operations are not considered, though these also
may eat significant processing power.

Your question isn't about the C programming language, nor about
any particular programming language, and probably belongs in a forum
like comp.programming.

... but for what it's worth, try the analysis yourself. Take
some simple algorithm, implement it, study the machine instructions
that it generates, and try to predict how much time it will take.
Don't forget to take account of pipeline parallelism, cache hits
and misses, translation look-aside buffer hits and misses, ... It
will be a difficult job, but perhaps you can get an answer after a
great deal of labor. And then you'll have an answer -- which will
go straight out the window as soon as you install a new compiler
version or change the compilation flags, or even add RAM. In other
words, all that enormous effort will produce, at best, an answer
that you can use only once and cannot transfer to the next machine.
 
L

luser- -droog

Why calculation of complexity of various algorithms(Linear search,
bubble sort) confined to number of comparisons, whereas the arithmetic
operations and other operations are not considered, though these also
may eat significant processing power.

vol. 1 of The Art of Programming by Don Knuth would be a good resource
for learning how to do this analysis on an idealized machine
architecture. Used copies (2nd Edition) are super cheap.
 
G

Gene

Why calculation of complexity of various algorithms(Linear search,
bubble sort) confined to number of comparisons, whereas the arithmetic
operations and other operations are not considered, though these also
may eat significant processing power.

You probably aren't reading the right sources. Analyzing comparisons
only is a convenience for the analyst. It lets him/her avoid defining
a model of computation. The embedded assumption is that the rest of
the computation will have run time proportional to that number, but
this may not be true as some have already pointed out.

A good algorithms text will begin by defining a model of computation
and then go on to define run time as the number of execution steps in
that model. Usually it's a Real RAM model. IIRC this is defined
early in Aho, Hopcroft and Ulman, for example.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top