HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Does an array count as a primitive operation when it is used as an argument in a function call?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
argumentarrayusedfunctionprimitiveoperationcalldoeswhencount

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#63751, answer score: 3

Revisions (0)

No revisions yet.