Skip to main content
Improved question
Source Link

KINDLY READ BEFORE MARKING AS DUPLICATE.

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 forby the time we reach $n$ we dohave $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.

KINDLY READ BEFORE MARKING AS DUPLICATE.

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 for $n$ we do $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.

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.

Source Link

Understanding time complexity of dynamic array implementation of stack

KINDLY READ BEFORE MARKING AS DUPLICATE.

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 for $n$ we do $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.