Midterm Flashcards
What is an algorithm?
Well defined computational
procedure, takes input, and generates
output
An algorithm is correct if…?
for every
input is halts with the correct output
Search algorithm?
method for finding an item or
group of items with specific properties within a
collection of items
Linear search?
Also known as brute force search, and list does not have to be sorted
Binary search must be what?
sorted to give correct answer
Linear Search first step?
Start from the leftmost element of a[] and one by one
compare x with each element of a[]
Linear Search second step?
if x matches with an element, return the index.
Linear Search third step?
if x doesn’t match with any of the elements, return -1
Time Efficiency of An
Algorithm formula?
T(n) ≈ cop ∗ C(n)
Best Case?
List is already sorted
Worst Case?
Needs to search every element/list is backwards
Average Case?
The average case efficiency is the time taken by the
algorithm for a typical/average input of size ‘n’. ?
Insertion sort?
To find the correct position for a card, compare it with each of the cards already in the hand, from right to left.
We usually consider the _____ running time for any input. This is
also often the expected running time.
Worst Case
it can be shown that the
average case for insertion sort is ____
quadratic
