0
$\begingroup$

let me tell you first what is written in the book I am following.

If the array is full,create a new array of twice the size, and copy items. At n=1,we do 1 copy operation,at n=2,we do 2 copy operation and at n=4 we do 4 copy operation and so on. By the time we reach n=32,the total number of copy operation is $1+2+4+8+16=31$ which is approximately equal to $2n$ i.e (32).

Ok ! so far I got it. My question is that can't we say that since by the time we reach $n$ we have $2n-1$ copy operations ,time complexity would be $O(2n-1)=O(n)$?

further the books says

we are doing the doubling operation $\log n$ times .(OK) For n push operations we double the array size $ \log n$ times .

here we performed 7 push operation and doubled the array $\log 16=4 $ times so what does the above statement say? Kindly help me calculate the running time in simplest way.

Improve this question
$\endgroup$
3
  • $\begingroup$ Are you saying that $n$ is the size of the array before copying? In that case you are doing $n$ copying operations, not $2n-1$. $\endgroup$
    – pdexter
    Commented Aug 19, 2016 at 9:47
  • $\begingroup$ I have edited the question.Please have a look again. $\endgroup$
    – Aditya pratap singh
    Commented Aug 19, 2016 at 9:51
  • 2
    $\begingroup$ OK, I read it. I'm voting to close as unclear. Who says the complexity isn't $O(n)$? And seven push operations causes three doublings, not four: $1\to2\to4\to7$, and $\lceil \log_2 7\rceil = 3$. $\endgroup$
    – David Richerby
    Commented Aug 19, 2016 at 9:54

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.