When calculating runtime dependence on the input, what calculations are considered? For instance, I think I learned that array indexing as well as assignment statements don't get counted, why is that?


When doing complexity calculations we generally use RAM model. In this model we assume that array indexing is O(1). Assignment statement is just like assigning some value to some variable ins array of variables. This is just for convenience. It simplifies analysis of the algorithm. In real world array indexing takes $\approx$ O(log I) where I is number of things indexed.

We generally consider things that depend on size of input e.g. loops. Even if there is O(1) operation in the loop and it is executed n times then algorithm runs for O(n) time.

But O(1) operation outside of loop take only constant time and O(n) + O(1) = O(n).

Read about radix sort algorithm from CLRS.

  • $\begingroup$ What about increments in a loops? Those should be O(n) right? $\endgroup$ – user8722 Jul 13 '13 at 6:01
  • $\begingroup$ for (int k=0; k<N; k++) {sum = sum + values[k];} Is the code in question. It was said to make 3N + 2 calls. $\endgroup$ – user8722 Jul 13 '13 at 6:01
  • $\begingroup$ Nope. For sum = sum + values[k], + is O(1) and = is also O(1). But the loop runs O(N) times. So its O(N) * O( 1 + 1) = O(N). O(3N+2) calls is just O(N). $\endgroup$ – Pratik Deoghare Jul 13 '13 at 6:03
  • $\begingroup$ But why is it O(3N + 2) calls? $\endgroup$ – user8722 Jul 13 '13 at 6:06
  • $\begingroup$ Accessing value[k] is 1 call. + is 1 call. = is 1 call. That explains 3 calls made N times but I don't know about +2. $\endgroup$ – Pratik Deoghare Jul 13 '13 at 6:12

The ultimate goal is "execution time in seconds" or more generally (disregarding modern CPU features) "number of clock cycles". As it turns out, this is hard to analyse, and it is also machine or at least instruction-set specific. Therefore, it is usually not done.

The next level of abstraction is to precisely count all operations (of some assembly-style pseudo code), keeping individual operation cost (in clock cycles) as parameters. Note that such analysis is found in Knuth's "The Art of Computer Programming" among others, so there certainly is a place for this kind of approach, even though it is hard and tends to be harder in presence of memory hierarchy.

Last but not least -- and certainly most prominent -- is analysis of dominant operations ignoring constant factors and asymptotically vanishing constributions ("$O$-analysis"). The reasoning is that runtime is bound to behave asymptotically like the number of most frequently executed operations, times some factor depending on the actual implementation and machine. This kind of analysis yields general results that apply to all machines (covered by the RAM model) and is easier to perform than the above. It can, however, lack specifity.

Leaving "classic" frameworks behind, many algorithms are dominated by memory and/or communication cost, so in that case counting the number and volume of memory acceses resp. network transmissions is reasonable (and maybe sufficient).

Furthermore, keep in mind that we are often not that interested in absolute performance of an algorithm but in comparing it to others. This, too, may inform the choice of analysed parameter.

So you see, there is no one definite answer. Depending on the goals of the analysis at hand, different answers can be given.

See also my answer here for some related thoughts, and Sebastian's answer on Quicksort for an example.

  • $\begingroup$ I am not content with saying that the most prominent approach you mention is entirely covered by the RAM model: The RAM model usually does not account uniform costs to multiplication (in order to retain the equivalence of problems solvable by TMs in poly-time with problems solvable by RAMs in poly-time). However, multiplication is usually assumed to cost a constant amount of time in the analysis of many algorithms $\endgroup$ – Cornelius Brand Jul 13 '13 at 18:20
  • $\begingroup$ @cbra: I have not encountered a RAM model with uniform cost for everything but multiplication. In particular, it is not necessary for poly-time-equivalence. $\endgroup$ – Raphael Jul 13 '13 at 22:06
  • $\begingroup$ I am not sure if I got you right, but when assigning uniform cost to multiplication, you can compute (thus, store) the number $2^{(2^n)}$ in $O(n)$ steps using repeated squaring. $\endgroup$ – Cornelius Brand Jul 14 '13 at 9:20
  • $\begingroup$ @cbra You seem to have a point there. The RAM model in "pure" form does not offer multiplication as an atomic action but implements it by repeated adding. Therefore, uniform cost for multiplication (and potentially other operations) is "dangerous" in that it breaks certain relations if applied to problems where number become large (i.e. larger than the input (?)). $\endgroup$ – Raphael Jul 15 '13 at 8:51

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy