4
$\begingroup$

Possible Duplicate:
How can we assume comparison, addition, … between numbers is $O(1)$

When we calculate the time-complexity of some algorithm we make many simplifications (or assumptions) on our calculation. For instance we say that assume basic arithmetic operations are all constant time and we assume reading/writing to a memory location is constant time.

I've worked on some algorithms where these assumptions don't hold. I'm looking for the background I need to properly approach/describe these algorithms. In particular I wish to know:

  1. What is the generic name for such a simplification/assumption?
  2. Is there a name for the basic model of simplifications we're using? (Assuming there is a common model)

Note: I've done work with cache-dependent/cache-oblivious algorithms. I understand how to calculate in that domain, but I'm lacking the terminology/background to properly compare/contrast such algorithm analyis with that which don't consider the cache.

Improve this question
$\endgroup$
2
  • $\begingroup$ You could take a look at accepted answer in this question. $\endgroup$
    – user742
    Aug 25, 2012 at 19:57
  • $\begingroup$ Though the question is phrased differently I'd say those answers are acceptable to my question. Feel free to close as duplicate. $\endgroup$
    – edA-qa mort-ora-y
    Aug 25, 2012 at 20:27

1 Answer 1

Reset to default
1
$\begingroup$

It is generally referred to as "Random Access Machine" or RAM model. This model assumes that accessing any unit of data, irrespective of its position or type, takes the same constant amount of time. Now, what you take as a "unit" of data is important. For all practical purposes, we may consider the primitive data types, integer, float and characters (but not strings) as a unit of data. A single instruction on unit data is considered to take constant amount of time.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm looking at the WikiPedia entry on RAM and I don't see how these leads us to treaing something like multiplication as constant time. $\endgroup$
    – edA-qa mort-ora-y
    Aug 25, 2012 at 13:53
  • $\begingroup$ Generally, the number of bits required for a particular primitive type is assumed to be constant. So, since operations like addition, subtraction, multiplication, etc. take time that is a function of the number of bits required, the time required to perform them is also considered to be constant. $\endgroup$
    – Arani
    Aug 25, 2012 at 14:28

Not the answer you're looking for? Browse other questions tagged or ask your own question.