Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
As pointed out by Raphael, it depends on the machine model. Under the assumptions of the RAM model of computation ...
- Simple operations (+, -, call, return, etc.) take one time step.
- Loops and subroutines are not simple operations: they may involve many of them.
- 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.
Sumdo?) That said, passing a pointer to a method is arguably not even an operation. $\endgroup$