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

yes they are same if we perform for only one element.

if we delete all elements , it will also cost O(n)+ O(1) + (n-2) + O(1)+ O(n-3) + O(1) + O(n-4) +.... .................O(1)= O(n²) right?

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

---

Yes @rishab right.

---

@arvin here is there any difference between extract and delete

---

@prince see extract means to take it out... And then U can do anything with that element. I mean U can modify it or insert it into another array or do anything as far as i have understand

.

But delete is u cannot make any good use of that element.

---

@arvin,

Why we have to shift the elements ?

we didn't use that array further then why to shift?

think if we want the array further use, even your array shifts on extracting element, we have to sort it anyway, in that case also there is no use of shifting.

think if we want the array further use, you inserted only decreasing order elements... then access array in circular fashion ...... in that case also there is no use of shifting.

 

any difference between extract and delete ?

as per my knowledge, i hope no difference between them ... we just interchange the words

 

---

@shaikh see the rule is that if u delete any element or you extract any element from any data structure than it should maintain the property of that data structure.

.

means if you delete or extract an element from an array than after doing that it should maintain the integrity of being an array. means the element should be stored from the base address only.

.

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

---

 @  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.