Operation time complexity for a LINKED LIST

The time complexity of handling the operations in a data structure like a LINKED LIST are as follows:

i. Most of the operations are O(n) [i.e. omega times n]
ii. Remove/Insert operations that handles element between elements require O(1) [i.e. omega times one] this is due to references/pointers on both the ends of the list, hence the elements don't require to be shifted. However, due to the references/pointers this data structure requires additional memory!

Operation time complexity for an ARRAY

The time complexity of handling the operations in a data structure like an ARRAY are as follows:

i. Almost all the operations are O(1) [i.e. omega times one]
ii. Remove/Insert operations that handles element between elements require O(n) [i.e. omega times n] because the elements need to be shifted.
Note! Hence, an array as a data structure is used where remove/insert operations are not required.

Selection Sorting An Array

Selection sorting an array A[0, 1, 2, ..., n-1]

01 SelectionSort(A[0, 1, 2, ..., n-1])
02 for (j <- 0) to (n-2) do
03 m <- j
04 for (i <- j+1) to (n-1) do
05 if A[m] > A[i] then
06 m <- i
07 end if
08 end for
09 exchange A[m] <-> A[j]
10 end for

Bubble Sorting An Array

Bubble sorting an array A[0, 1, 2, ..., n-1]

01 BubbleSort(A[0, 1, 2, ..., n-1])
02 i <- 0 03 repeat 04 exch <- False 05 for (j <- 0) to (n-2-i) do 06 if A[j] > A[j+1] then
07 exchange A[j] <-> A[j+1]
08 exch <- True
09 end if
10 end for
11 i <- i+1
12 Until exch = False

Click here for explanation on what is bubble sort?

Computing The Median of An Array

Pseudocode for computing the median of an array A[0, 1, 2, ..., n-1]

01 SelectMedian(A[0, 1, 2, ..., n-1])
02 BubbleSort(A) or SelectionSort(A)
03 if n is odd then
04 r <- A[(n-1)/2]
05 else
06 r <- (A[n/2] + A[(n/2)-1)])/2
07 end if
08 return r