I'm quite confused about something.

*So I have an algorithm which takes as input $k!$ numbers, let's call them $x_1, x_2, \ldots, x_{k!}$.

*Then, in the algorithm, a 'matrix' is defined: i.e. for each $i$ and $j$ ($i$ from $1$ to $k-1$, $j$ from $1$ to $k$) a number R_{i,j} is defined by adding $(k-1)!$ numbers (each of which is in $\{x_1, x_2, \ldots, x_{k!}$, but this is not relevant for all I know) together.

*Then a similar construction is done: a new 'matrix', as above, is defined, but now each of the $k(k-1)$ elements (of the matrix) are obtained by adding $k$ numbers.

*Finally, $k-1$ elements are defined, each of which is obtained by adding up $k-1$ numbers, each of which is a multiplication of precisely two numbers. (So it is like this: for example the first of these k-1 elements is $a_1 = t_1 l_1 + t_2 l_2 + \cdots + t_{k-1} l_{k-1}$.)

That is basically my algorithm.

So what's the complexity of it? Do I have to count both the sums as the multiplications? I added up (k-1)! in the algorithm, so I guess it will be $O(k!)$!? I was said that 'only multiplications' need to be counted. Also, do I have to "count" assignments?

So, in general, how do you compute the computational complexity of an algorithm such as this one; it should be fairly easy, as only multiplications and sums are done...

  • $\begingroup$ (This is Rogier Spilliaert again.) Thanks for your answer. I understand what you are saying. However, I still have problems. 1) It is, indeed, obvious that my first step is the most 'demanding': by the way, I think that my first step may be $O((k-1) k!)$ only (because a sum of $a$ terms only requires $a-1$ additions, I guess, and yes I have also counted 'assignments'). 2) So, you are saying that $O(k(k-1) k!)$. I guess this implies that it is not a polynomial time algorithm!? 3) I am, however, still confused. My input are $t:= k!$ numbers, and for constructing my first matrix I do order $(k-1) $\endgroup$ – Dorry Sep 15 '12 at 13:03
  • 1
    $\begingroup$ your accounts have been merged. I would suggest that you register your account if you plan on continuing to use the site; it will allow you to make comments properly. $\endgroup$ – Qiaochu Yuan Sep 22 '12 at 8:28

The computational complexity really depends on the model of computation. In your case, the intended model is probably the "RAM machine" (or "pointer machine") with integers of unbounded length. This means that you can assume that your program is written in C, and each of the following operations has unit cost: arithmetic operations, array indexing, assignment, comparison, logical operations, if, for, function call, and so on.

But aren't some of these operations more complicated than the rest? That's true, but it's not going to matter, since you're not going to count the actual exact number of operations. Rather, you'll be using an asymptotic estimate of the form $O(f(k))$ (and its siblings), that "hides" a constant factor. That is, if (say) $g(k)/7 \leq f(k) \leq 12g(k)$ then $O(f(k))$ and $O(g(k))$ mean the same thing. So the basic cost of the operations doesn't matter. (I'm assuming you've been introduced to this notation.)

In your case, the most expensive operation is constructing the first matrix, which takes time $O(k(k-1)\cdot k!)$. All other operations are much cheaper, and therefore they do not affect the asymptotic running time. (A similar situation: $n + \sqrt{n} = O(n)$.)

Now there is some cheating involved, since in real life arithmetic operations are done only on machine integers, and so they take more time when the integers in question become bigger. This is ignored however in the RAM machine model (usually). In contrast, in the Turing machine model, memory access doesn't take constant time - we say that it is not $O(1)$ (since $O(1)$ is the same as a constant).


Your Answer

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

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