algorithm self doubt

Question

suppose we are given a sorted array ....and we need to extract minimum every tym  what is the time complexity??

and what is the tym complexity to delete the minimum ? are they both same ??

and what is the tym complexity to delete an element?

Answer 1

suppose the array is sorted in ASCENDING ORDER : 

--------------------------------------------------------------------------------------------

1)to extract one minimum time taken is O(1) but than all the elements will be shifted which will cost O(n-1).

similarly if we extract all elements it will cost O(n-2) + O(1)+ O(n-3) + O(1) + O(n-4) +.... .................O(1)= O(n²)

-----------------------------------------------------------------------------------------------

2)to delete the minimum O(1) to delete and O(n-1) to left shift all element. = O(n) . yes they are same if we perform for only one element.

-----------------------------------------------------------------------------------------------

3) to delete maxm element : O(1)

    to delete any specific element(worst case  = O(n) 

----------------------------------------------------------------------------------------------

Comments

 @  arvin  why we need to shift after taking min cant we do in O(1) becz we know where is minimum every time am  i correct  Shaik Masthan???

 

                                                  

 

 

 

---

@eyeamgj

yes... my approach is that one.

@arvin

moreover extract and delete may seem same but they both are different.

i read what you replied for Prince Sindhiya question,

if delete doesn't return the element then there is difference, but who says delete is doesn't return that element ( is there any standard reference ) ?

means the element should be stored from the base address only.

so you are saying that, " i don't bother about the last cells of array but i bother about first cells of array "

note that every cell of the array is same priority.

and moreover that statement leads to a[0] should have initialized and must be used, but unfortunately i didn't read any where it ( i am saying it is conventional but not the rule. )

i.e.,

char k1[]="SHAIK "; ===> whenever you are accessing, then just start index with 0

char k2[]=" SHAIK"; ===> whenever you are accessing, then just start index with 1,

in this case k1 and k2 are equal but note tha we have to take care of indexes correctly.

let index of k1=i and index of k2=j

j=( ( i + 1 ) % sizeof(k1) )

---

@shaikh delete is an operation that has been defined. means you have no use of this value or you dont need it at all.

but extract means that it has been only removed from it and it may be still there.

see you know that the array has been performed with extract or delete. but how the array will know that it has been operated. suppose a new user comes and he is unaware about the operation done on array .

how will he access minimum value just by accessing 0th element but it will be null means array is empty.... and they havent told that you have to use a variable that will keep track of elements being deleted.

.

char k1[]="SHAIK "; ===> whenever you are accessing, then just start index with 0

char k2[]=" SHAIK"; ===> whenever you are accessing, then just start index with 1,

on this see. k1 and k2 are entirely different as they are not sorted.

for k1[]="1234.

k2[]=" 1234..."  see in k2 how can you say its sorted... your array starts from a[0] not from a[1] . this is the rule array always starts from base address.