patternMinor
Does an array count as a primitive operation when it is used as an argument in a function call?
Viewed 0 times
argumentarrayusedfunctionprimitiveoperationcalldoeswhencount
Problem
Say I have
I counted the following primitive operations:
I know accessing a certain index in A counts as 1 primitive operation, but I am not sure about
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 7I 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?Solution
As pointed out by Raphael, it depends on the machine model. Under the assumptions of the RAM model of computation ...
... 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
- 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.Context
StackExchange Computer Science Q#63751, answer score: 3
Revisions (0)
No revisions yet.