2.3.1 Time complexity

• Big-O Notation

  
• Steps of a Binary search:

  • Find the middle point of the system by N/2
  • Compares it to the middle value
  • If it is the middle value then return True
  • If not, compare if it is larger or smaller then the middle value and update the pointers as necessary. Discard relevant side of list
  • Repeat until item is found or the end of the list is reached
  • Return False if item is not found
  • O(logn)
• Bubble Sort

  passes through list and compares pairs to check if second item in pair is the largest of the two.

  Time complexity O(n^2)

  
• Binary Search

  Divide and conquer

  
• Linear Search Algorithm

  traverses through every item one at a time until it finds the item it is searching for

  O(n) Big-O notation

  
• When developing an algorithm there are two different things to check:

  • Time Complexity
  • Space Complexity
• Time Complexity

  • how much time it requires to solve a particular problem
  • measured using big-o notation, which shows the effectiveness of the algorithm.
• Constant Time Complexity

  • O(1)
  • Unrelated to the number of items inputted
  • Always will take the same amount of time to complete regardless of the number of values inputted
• Linear Time Complexity

  • O(n)
  • The time taken to complete the algorithm is related to the number of items inputted
• Ranking Time Complexities

  
• Space Complexity

  • the amount of storage the algorithm takes
• To reduce space complexity

  • make sure you perform all the changes on the original pieces of data

  To reduce time complexity

  • try to reduce the number of embedded loops as possible