1
$\begingroup$ 
int[] arr = new int[10];

Would this count as a single primitive operation under the RAM model or would it be 10 operations as we are allocating 10 memory locations to this variable "arr"?

This also ties in to my other question: if there existed an array of size 1 and we were to increase the size by 1 and copy over the elements continuously, why is the Big-Theta of this computation θ(n^2)?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ May I ask, why it matters for your follow up question if the cost of allocation is non-constant? As I understand the 2nd question, its all about resizing the array by increasing its size 1 at a time. If this is so, you can actually ignore the cost of the allocation, and by merely counting the total cost of moving elements from the smaller to the larger array, should be enough to have $\Theta(n^2)$ bound. $\endgroup$
    – Russel
    Jun 30, 2022 at 15:20
  • 2
    $\begingroup$ The RAM model typically doesn't intrinsically support the heap. $\endgroup$
    – Yuval Filmus
    Jun 30, 2022 at 15:42

0

Reset to default

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.