Complexity of data structure

Discussion in 'C Programming' started by C learner, Apr 24, 2011.

  1. C learner

    C learner Guest

    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.
    C learner, Apr 24, 2011
    #1
    1. Advertising

  2. C learner

    Ian Collins Guest

    On 04/24/11 07:13 PM, C learner wrote:
    > 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.

    --
    Ian Collins
    Ian Collins, Apr 24, 2011
    #2
    1. Advertising

  3. C learner

    Eric Sosman Guest

    On 4/24/2011 3:13 AM, C learner wrote:
    > 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.

    --
    Eric Sosman
    d
    Eric Sosman, Apr 24, 2011
    #3
  4. On Apr 24, 2:13 am, C learner <> wrote:
    > 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.
    luser- -droog, Apr 25, 2011
    #4
  5. C learner

    Gene Guest

    On Apr 24, 3:13 am, C learner <> wrote:
    > 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.
    Gene, Apr 25, 2011
    #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:
    328
  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:
    536
    clintonG
    Apr 22, 2005
  3. Frank D. Greco
    Replies:
    0
    Views:
    331
    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:
    379
    Thomas G. Marshall
    Jul 13, 2005
  5. A
    Replies:
    27
    Views:
    1,574
    Jorgen Grahn
    Apr 17, 2011
Loading...

Share This Page