Search Algorithms

Question 1

List and Describe search algorithms (2)

Answer 1

1. Linear search
   Start at the edge of the list. Check if the current number is the wanted number. If not go to the next number.
2. Binary search
   Sorted list is needed. Start in the middle. If wanted number is smaller than middle then compare against number in the half of the first half (25% of all list). If wanted number is greater than middle then compare against number in the half of the second half (75% of all list). Continue this method until the desired number is acquired.

Extra info:
For list of n elements: find middle by using ceiling of (n-1)/2.
Ceiling means that if number from equation is not an integer choose the next larger integer. Example: if 2.3 then choose 3

So if you have 4 elements in your list you will get 1.5 then 2 from equation. First element of list is always 0. So you will compare against the 3rd element.

Question 2

Linear search: performance

Answer 2

1. Best case: O(1)
2. Worst case: O(n)
3. Average case: O(n)

Question 3

Binary search: performance

Answer 3

1. Best case: O(1)
2. Worst case: O(log(n))
3. Average case: O(log(n))

Question 4

What is Intermezzo?

Answer 4

Graph representing the time complexity (big O) of algorithms in order to compare their performance (how much time, memory, disk etc.)

Used to classify algorithms.
Comparison according to rates of growth.
Useful: analyzing efficiency