Complexity2

Question

An array of size n. Find the time complexity to insert a new value before an element e in the array?

a)O(n)

b)O(log n)

c)O(1)

Comments

O(n)...?

---

Since array may be unsorted here finding perticular elemnt itself take O(n) time . but array property is continuous  memory allotment means no gap present between so to insert ans element may require shifting of n-1 element . so total O(n) +O(n)= O(n)

Answer 1

Since array may be unsorted here finding perticular elemnt itself take O(n) time . but array property is continuous  memory allotment means no gap present between so to insert ans element may require shifting of n-1 element . so total O(n) +O(n)= O(n)

Comments

@saurabh

why it is not O(n²)

---

@Kapil @Sourabh

see say an element in the middle of the unsorted array.

So, n/2 time to find it.

Now, need to shift n/2 elements.

So, n/2*n/2=O(n²) complexity

Where is it incorrect?

---

+ means OR

is it for OR

or AND will work good here?

---

@srestha shifting n/2 elements once just required a for loop with n/2 swaps

Answer 2

The element to be inserted must be inserted at one particular location of the array.

It may require shifting all the subsequent elements by one position. 

It may take O(n) time 

This article about search data structure is good one :)

https://en.wikipedia.org/wiki/Search_data_structure