Week 3 - Algorithms Flashcards
What can computer do with an array?
it can only look at the elements inside of it one at a time
What does Big O notation mean?
it describes the running time and it means “on the order of” something so we use it as an efficiency criterion to compare different logarithms. in other words, it means the “WORST Case” for the algorithm
The types of Big O notation are:
O (n^2)
O(n \log n)
O(n)
O(\log n)
O(1)
What does Ω mean?
Omega notation describes the lower bound of the number of steps for our algorithm, or how few steps it might take. in other words, it means the “BEST Case” for the algorithm
What does Θ mean?
it describes the running times of algorithms if the upper bound (Big O) and lower bound (Ω) are both the same.
What are the types of searching algorthims?
Linear Search
Binary Search
What does the Linear search algorithm do?
it goes through each element of a list until the desired element is found, and it will continuously repeat itself till the end of the data set. Known as the easiest searching algorithm.
What does the Binary search algorithm do?
it is used in a sorted array or list by starting in the middle and repeatedly dividing the problem in half each time till the end of the data set. Which is much faster than linear search.
What are the requirements of Binary search?
Data need to be sorted.
(and to sort data we need lots of memory)
What are the types of sorting algorthims?
Selection sort
Bubble sort
Merge sort
What does the Selection Sort algorithm do?
it sorts an array by repeatedly finding the smallest element from the unsorted part and putting it at the beginning (the sorted part)
What does the Bubble sort algorithm do?
it sorts an array by repeatedly comparing each pair (2) of elements and swapping the smallest element of them to the left
