0
$\begingroup$

This is from the Narasimha's data structure book

For nth element (n - 1 index), if we want to push an element, create a new array of size n and copy old array to the new, and at the end assign the value of n-1 index.

After n push operations the total time T(n) is proportional to 1 + 2 + 3 + 4 .... + n ≅ $O(n^2)$.

Shouldn't it be O(n), or I am missing something.

$\endgroup$
1
  • 1
    $\begingroup$ The total number of elements copied is about n^2 / 2. Every single push operation is O(n), n push operations are O(n^2). $\endgroup$
    – gnasher729
    Nov 15, 2023 at 11:29

2 Answers 2

1
$\begingroup$

The time for pushing in a stack of size $k$ is $O(k)$. Thus the cost of all of the pushes is:

$$\sum_{k=1}^{n} k \ = \ \frac{n(n+1)}{2} \ = \ O(n^2) \ .$$

$\endgroup$
1
  • $\begingroup$ Oh, that was sum of $n$ natural numbers. How embarrassing 😅. Thank you $\endgroup$
    – tbhaxor
    Nov 15, 2023 at 13:28
0
$\begingroup$

People have already explained that the time complexity is O(n^2). I will add something extra to this.

In real life, array storage is not incremented by the size of 1 element.

What happens is that if you have K items in the array and then when the time comes for allocation of new storage (for new elements) then the array will be grown to some N times K.

So, if N is 1.5, then the size of the new array will be N x K x Size_of_1_element. This is done so that time is not wasted in allocating storage. However, it is quite possible that all the allocated storage may not be used. So, its a space vs time tradeoff. However, it had been decided by computer language inventors that wasting some storage is better than wasting time in frequent allocation of storage.

In Java language, N is 1.5 but other languages may have different values of N.

$\endgroup$
2
  • $\begingroup$ It’s not a matter of the language, but the library used. I used one library where you could at creation time how much memory would be allocated, so if you knew you had to store 15,370 items you said “create an array with space for 15,370 items” (and the library allocated about a percent more because some people are bad at counting). $\endgroup$
    – gnasher729
    Dec 13, 2023 at 17:13
  • $\begingroup$ Dynamic array list/vector is in-built in Java language. It doesn't use any library to provide these features. Same goes for C++. Vector is in-built in C++. I don't know with which language you used the library (may be with C language because it doesn't provide dynamic array/vector implementation). $\endgroup$
    – Andrew
    Dec 18, 2023 at 12:19

Your Answer

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

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