4
$\begingroup$

Say I have return A[n-1] + Sum(A, n - 2). I counted the following primitive operations:

return A[n-2] + Sum(A, n - 2)
   1    2 3   4  5  6   7

I know accessing a certain index in A counts as 1 primitive operation, but I am not sure about A in the function call. Did I count the right number of operations?

$\endgroup$
1
  • $\begingroup$ Depends on your machine model and cost function. There is no single correct answer. (What does Sum do?) That said, passing a pointer to a method is arguably not even an operation. $\endgroup$
    – Raphael
    Sep 21, 2016 at 21:39

1 Answer 1

3
$\begingroup$

As pointed out by Raphael, it depends on the machine model. Under the assumptions of the RAM model of computation ...

  1. Simple operations (+, -, call, return, etc.) take one time step.
  2. Loops and subroutines are not simple operations: they may involve many of them.
  3. Memory accesses (e.g., indexing into an array) take one time step.

... you counted correctly operations [1-4] and 7. As for operation 5, it depends: the subroutine call does count as one single-step operation (according to assumption 1), but the subroutine itself doesn't: it is a composite operation (according to assumption 2). Finally, I would not consider passing A as a parameter to be an operation: A affects running time when it is accessed within the Sum subroutine, not in the subroutine call.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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