-
Greedy Algorithm
Summary
-
Divide and Conquer Algorithm
Summary Algorithm Divide Step Conquer Step Combine Step Time Complexity Merge Sort Split array into halves Recursively sort each half Merge sorted halves O(n log n) Quick Sort Partition array around a pivot Recursively sort left and right No additional work needed O(n log n) avg, O(n^2) worst Binary Search Find middle element Recursively search…
-
Data Structures
Summary Linear Data Structures Linear data structures organize elements sequentially, where each element has a unique predecessor and successor (except the first and last elements). Examples: Arrays: A collection of elements stored in contiguous memory locations. Operations: Access: O(1) Search: O(n) Insertion/Deletion: O(n) (in the worst case, due to shifting). Example Linked Lists: A sequence…
-
Algorithm Analysis
Summary ✔ Algorithm analysis helps evaluate performance using time and space complexity.✔ Order of growth determines how an algorithm scales with input size.✔ Asymptotic analysis generalizes efficiency across different hardware.✔ Worst-case complexity (Big O) is the most important for real-world scenarios.✔ Big O, Big Ω, and Big Θ describe different efficiency bounds.✔ Mathematical foundations (asymptotic…
-
Logarithm
Definition of Logarithm:\(\text{If and only if } y = a^x ), where ( a > 0 ), ( a \neq 1 ), and ( x > 0 \)\(\log_a y = x \) Types of Log:1. Common log ( \(\log_{10} x \) )Also written as \(\log x \)2. Natural log ( \(\log_{2.71828} x \) )Also written…
-
Limits & Continuity
Limit of a Constant:\( \lim \limits_{x \to a} c = c \) \( \lim \limits_{x \to a} x = a \)\(\lim \limits_{x \to a} \frac{x^n-a^n}{x-a} =na^{n-1} \)\(\lim \limits_{x \to a} \frac{x^m-a^m}{x^n-a^n} =\frac{m^{m-n}}{n} \)\(\lim \limits_{x \to 0} \frac{a^x-1}{x} = \ln a \) Exponential Functions:\( \lim \limits_{x \to a} e^x = e^a \)\( \lim \limits_{x \to 0}…
-
Integration
Constant Rule:\( \int k \, dx = k x + C \) Constant Multiple Rule:\( \int k \cdot f(x) \, dx = k \int f(x) \, dx\) Power Rule:\( \int x^n \, dx = \frac{x^{n+1}}{n+1} + C \quad \text{for } n \neq -1 \) \( \int (ax+b)^n \, dx = \frac{(ax+b)^{n+1}}{a(n+1)} + C \) Exponential…
-
Derivatives
Power Rule: \( \frac{d}{dx} \left[ x^n \right] = n x^{n-1} \) Constant Rule: \( \frac{d}{dx} \left[ c \right] = 0 \) Constant Multiple Rule: \( \frac{d}{dx} \left[ k f(x) \right] = k \frac{d}{dx} f(x) \) Exponential Functions: \( \frac{d}{dx} \left[ e^x \right] = e^x \)\( \frac{d}{dx} \left[ e^{(ax+b)} \right] = ae^{(ax+b)} \)\( \frac{d}{dx} \left[ a^x…