Complexity in array

Basic complexity of array is describe here shortly.

1. Data Structures & Algorithms Complexity in Array

2. Array Array Consecutive group of memory locations Same name and type ( int , char , etc.) To refer to an element Specify array name and position number (index) Format: array_name [ position number ] First element at position 0 N-element array c c[ 0 ] , c[ 1 ] … c[ n - 1 ] Nth element as position N-1 c[6] -45 6 72 1543 -89 62 -3 1 6453 78 Name of array (All elements of this array have the same name, c ) c[0] c[1] c[2] c[3] c[11] c[10] c[9] c[8] c[7] c[5] c[4] Position number of the element within array c

3. Complexity The complexity of an algorithm is a function describing the efficiency of the algorithm in terms of the amount of data the algorithm must process. There are two main complexity measures of the efficiency of an algorithm: Time complexity: is a function describing the amount of time an algorithm takes in terms of the amount of input to the algorithm. Space complexity: is a function describing the amount of memory (space) an algorithm takes in terms of the amount of input to the algorithm. Time and space To analyze an algorithm means: developing a formula for predicting how fast an algorithm is, based on the size of the input ( time complexity ), and/or developing a formula for predicting how much memory an algorithm requires, based on the size of the input ( space complexity ) Usually time is our biggest concern Most algorithms require a fixed amount of space

4. Average, best, and worst cases Usually we would like to find the average time to perform an algorithm However, Sometimes the “average” isn’t well defined Example: Sorting an “average” array Time typically depends on how out of order the array is How out of order is the “average” unsorted array? Sometimes finding the average is too difficult Often we have to be satisfied with finding the worst (longest) time required Sometimes this is even what we want (say, for time-critical operations) The best (fastest) case is seldom of interest Common time complexities BETTER WORSE O(1) constant time O(log n) log time O(n) linear time O(n log n) log linear time O(n 2 ) quadratic time O(n 3 ) cubic time O( n k ) polynomial time O(2 n ) exponential time

5. Space Complexity Space complexity : The amount of memory required by an algorithm to run to completion the most often encountered cause is “memory leaks” – the amount of memory required larger than the memory available on a given system Some algorithms may be more efficient if data completely loaded into memory Need to look also at ‘system limitations’ e.g. Classify 2GB of text in various categories – can we afford to load the entire collection?

6. Array  Operations Following are the basic operations supported by an array . Traverse  − print all the array elements one by one. Insertion  − Adds an element at the given index. Deletion  − Deletes an element at the given index. Search  − Searches an element using the given index or by the value. Update  − Updates an element at the given index . Sorting  − Arranging the elements in some type of order.

7. Array Traverse Time complexity in Traverse In array the individual elements are typically stored in consecutive memory locations. So the complexity is O(1) . It is both for average and worst case. Begin at the first element. Repeat until there are no more elements. Process the current element. Move to the next element.

8. First Insert Adding an element to beginning of an array is O(n) - it would require to shift all the existing elements by one position. All elements in an array list are stored in a contiguous memory location. If we add more elements than the current size of the array - it will be grown automatically to accommodate the new element . Time complexity in First Insert Insertion of an element in the first position of an array . Need to shift all the existing elements by one position.

9. Last Insert Insertion of an element in the last position of an array. No need to shift all the existing elements by one position. Time complexity in Last Insert Addition to the end is O(1) amortized over multiple insertions for unsorted array . O(n) for sorted array .

10. Before Insert Adding an element before the particular position of an array is O(n) - it would require to shift the existing elements by one position which are after the desired position. S ame both for average and worst case. Insertion of an element before the desired position of a array . Need to shift the existing elements by one position which are after the desired position. Time complexity in Before Insert Element 4 is to be inserted before 6

11. After Insert Adding an element before the particular position of an array is O(n) - it would require to shift the existing elements by one position which are after the desired position. Same both for average, and worst case. Need Insertion of an element after the desired position of an array. Need to shift the existing elements by one position which are after the desired position. Time complexity in Before Insert Element 4 is to be inserted after 3

12. First D elete Deletion of an element from the first position of an array. Need to move everything after the deleted element back one space to the left. Time complexity in First Delete Delete from the first position, we'll have to move all n-1 remaining elements over, giving us  O(n)  for our worst case.  Same both for average, and worst case.

13. Last Delete Deletion of an element from the last position of an array . No need to move everything after the deleted element back one space to the left . Time complexity in Last Delete Delete from the  last  position, that just takes constant time. O(1) for unsorted array. O(n) for sorted array.

14. Particular Delete Deletion of an element from the particular position of an array . Need to move everything after the deleted element back one space to the left. Time complexity in Particular Delete Delete from the particular position, we'll have to move all n-1 remaining elements over, giving us  O(n)  for our worst case.  Same both for average, and worst case. Element 3 is to be deleted

15. B efore Delete Delete before the particular position, we'll have to move all n-1 remaining elements over, giving us  O(n)  for our worst case.  Same both for average, and worst case. Deletion of an element before the particular position of an array . Need to move everything after the deleted element back one space to the left. Element before 6 is to be deleted Time complexity in Before Delete

16. After Delete Delete after the particular position, we'll have to move all n-1 remaining elements over, giving us   O(n)  for our worst case.  Same both for average, and worst case. Deletion of an element after the particular position of an array. Need to move everything after the deleted element back one space to the left. Element after 2 is to be deleted Time complexity in After Delete

17. Searching Algorithms , Complexity Linear search Class Search algorithm Data structure Array Worst-case performance O ( n ) Best-case performance O (1) Average performance O ( n ) Worst-case space complexity O (1) iterative Binary search Class Search algorithm Data structure Array Worst-case performance O (log  n ) Best-case performance O (1) Average performance O (log  n ) Worst-case space complexity O (1)

18. Array Sorting Algorithms , Complexity Algorithms Time Complexity Space Complexity Best Average Worst Worst Quick sort O ( n log(n)) O ( n log(n)) O(n^2) O(log(n)) Merge sort O ( n log(n)) O ( n log(n)) O(n log(n)) O(n) Tim sort O ( n) O ( n log(n)) O(n log(n)) O(n) Heap sort O ( n log(n)) O ( n log(n)) O(n log(n)) O(1) Bubble Sort O ( n) O ( n^2) O(n^2) O(1) Insertion Sort O ( n) O ( n^2) O(n^2) O(1) Selection Sort O ( n^2) O ( n^2) O(n^2) O(1) Tree Sort O ( n log(n)) O ( n log(n)) O(n^2) O(n) Shell Sort O ( n log(n)) O ( n(log(n))^2) O(n(log(n))^2) O(1) Bucket Sort O ( n+k ) O ( n+k ) O(n^2) O(n) Radix Sort O ( nk ) O ( nk ) O(nk) O( n+k ) Counting Sort O ( n+k ) Θ( n+k ) O(n+k) O(k) Cube sort O ( n) Θ( n log(n)) O(n log(n)) O(n)

19. At a Glance Data Structure Time Complexity Space Complexity Average Worst Worst Access Search Insertion Deletion Access Search Insertion Deletion Array O (1 ) O ( n) O ( n) O ( n) O(1) O(n) O(n) O(n) O(n) Data Structure Insert Delete Balance Get at index Search Find minimum Find maximum Space usage Unsorted  array O (1) O (1 ) N/A O (1) O ( n ) O ( n ) O ( n ) O ( n ) Sorted array O ( n ) O ( n ) N/A O (1) O (log  n ) O (1) O (1) O ( n )