2.3.1 Analysis, Design and Comparison of Algorithms

• When developing an algorithm the two things to look at is

  time complexity and space complexity.
• Linear time complexities can be represented by o(n). It occurs when the time taken to complete an algorithm is directly proportional to the size of the input
• Polynomial time complexities can be represented by o(n^n). It occurs when the time taken to complete an algorithm is directly proportional to the size of the input to the power of n.
• Logarithmic time complexities can be represented by o(log n). It occurs when the time taken to complete an algorithm will increase at a smaller rate to the elements that are inputted.
• The big o notation would be a linear time complexity or o(n)

  
• The big o notation would be a polynomial time complexity or o(n^n)

  
• The big o notation for a divide and conquer algorithm would be o (log n)
• Space complexity of an algorithm is the amount of storage the algorithm takes
• If you have a lot of data to process, say for a future update, time complexity would be more important than space complexity
• if you have a lot of processing power, then time complexity is not as important. Instead you should focus on space complexity to make sure you are not wasting data often.
• To reduce space complexities ensure to perform all the changes on the original piece of data.
• To reduce time complexities ensure to reduce the number of embedded loops as possible-for example use a divide and conquer algorithm.
• This is a linear search algorithm due to having a single while loop in it. It searches through every element until finds what it is searching for.

  
• This is a binary search algorithm-which is a divide and conquer algorithm. This means it splits the list into smaller lists till it finds what it is searching for hence the line where it does /2.

  
• This is a bubble sort algorithm. It is a simple sorting algorithm that works by repeatedly swapping the elements in a list in order until it is sorted. The time complexity is o (n^2) hence the while loop and the if loop (which is a nested loop)