Algorithms

Linear search

• Searching through an unordered list by checking every item, in sequence, to see if it is the desired item.

• Worse case scenario has O(n) time complexity, best case is O(1)

• Space complexity is O(1)

Binary search

• Searching through an ordered list by calculating a midpoint position, checking the item and setting a new midpoint to continue comparisons

• Worst case scenario has O(lg n) time complexity, best case is O(1)

• Iterative binary search as O(1) space complexity, and recursive has O(lg n) space complexity

Binary search tree

• A rooted tree where the nodes are ordered

• Balanced trees: O(lg n) time complexity

• Unbalanced trees: O(n) time complexity

• Both have O(lg n) space complexity

Considerations you should have when choosing a data structure

• Keeping data maintained

• Adding, deleting, updating and sorting data

How does working with arrays change depending if it’s ordered or not?

• Ordered:

• To add a new item, the specific position will have to be searched for

• To delete and update an item, a binary search will need to be done

• Doesn’t need to be sorted

• Unordered:

• To add an item, it will be added at the end of the list

• For deleting and updating, linear search will be needed

• Sorting algorithms will be needed

How does working with hash tables change depending if it’s ordered or not?

Hash tables are always ordered

How do you work with a hash table?

• To add a new item, you would use the hashing algorithm

• Deleting and updating an item would use the hashing algorithm

• No sorting would be needed.

How do you work with binary search trees?

• You can add, delete or update items by using the binary search

• No sorting is needed

How does working with linked lists change depending if it’s ordered or not?

• Ordered:

• Linear search will be needed to locate the correct position

• Linear search will be needed to delete and update items

• No sorting needed

• Unordered:

• Items can easily be added infront of the list

• Linear search will be needed to delete or update nodes

• Sorting the list would require to traverse the list, write each element in an array and use an algorithm on said array

Bubble sort and example of {9,3,10,2,8,5,1}

• Compares each element of the list in “passes”

• First pass: {3,9,2,8,5,1,10}

• Second: {3,2,8,5,1,9,10}

• …

Bubble sort complexity

• Time complexity: O(n²)

• Space complexity: O(1)

Insertion sort and example of {2,8,5,3,9,4}

• Compares the left-most element with the other elements to the left, and sorts it

• 1st iteration: {2, 8, 5, 3, 9, 4}

• 2nd: {2, 8, 5, 3, 9, 4}

• 3rd: {2, 5, 8, 3, 9, 4}

Insertion sort complexity

• Time complexity: O(n²)

• Space complexity: O(1)

Merge sort and example of {2,8,5,3,9,4,1,7}

• Continuously dividing an array into sections of n/2 arrays, until they have individual items, then recreating arrays whilst comparing them

• Divide: {2}, {8}, {5}, … , {7}

• Merge: {2,8}, {3,5}, {4,9}, {1,7}

• Merge: {2,3,5,8}, {1,4,7,9}

• …

Merge sort complexity

• Time complexity: O(nlg n)

• Space complexity: O(n)