Algorithms and Complexity Flashcards

Flashcards covering Sentinel and Binary Search Algorithms, and the Growth of Functions.

In the worst case, what is the overall program time for a Linear Search?

T(N) = 3N+3

What is Sentinel Search?

A type of Linear search where the number of comparisons is reduced as compared to the linear search.

What is the number of instructions for Linear search (Worst-case)?

3N+3

What is the number of instructions for Sentinel search (Worst-case)?

2N+3

What is the time complexity of Linear and Sentinel Search?

Both have linear time complexity.

On what type of array does Binary Search work?

Sorted arrays

What does Binary Search do?

Locates a target value in a sorted array by successively eliminating half of the array from consideration

What is the time complexity of Binary Search in the worst case?

Logarithmic: T(N) = 1 + 2

What is the time complexity of Binary Search in the best case?

Constant: T(N) = 1

When is Binary Search more efficient?

Binary search algorithm is more efficient comparing to Linear and Sentinel Search algorithms (Binary logarithmic in worst case), but the input array should be sorted

What is important when comparing algorithms?

The growth of time complexity with increasing input size ‘n’

List functions from slowest to fastest growth.

Constant growth, Logarithmic growth, nc (where 0<c<1), Linear growth, n log n, Quadratic growth, n2 log n, Cubic growth, nc Polynomial growth (c is a constant number), Exponential growth, Factorial growth