Algorithmic Strategies - Formula Sheet

Essential Formulas and Complexities

1. Search Comparison Formulas

Average Comparisons in Sequential Search:

Average Comparisons = (n + 1) / 2

Where n represents the total number of elements in the search list.

2. Complexity Bounds

Linear Search Time Complexity:

• Best Case: O(1)
• Worst Case: O(n)
• Average Case: O(n)

Binary Search Time Complexity:

• Best Case: O(1)
• Worst/Average Case: O(log n)

Sorting Time Complexities (Bubble, Selection, Insertion Sorts):

• Best Case (Optimized Bubble/Insertion): O(n)
• Worst/Average Case: O(n^2)

3. Space Complexity Components

The total memory required by an algorithm is represented as:

S(P) = C + S_P(I)

Where:

• C: The fixed part representing memory space required for simple variables and constants.
• S_P(I): The variable part representing space required by variables whose size depends on the problem instance characteristics (such as recursive stack space).

4. Fibonacci Sequence Formula

The mathematical recurrence relation used in the dynamic programming approach for Fibonacci series generation is:

Fib(n) = Fib(n-1) + Fib(n-2)

With base cases defined as Fib(0) = 0 and Fib(1) = 1.