Section 25.14 Vocabulary and Common Recurrence Relations
Subsection 25.14.1 Common Recurrence Relations
Here again is the table of common recurrence relations from Table 25.12.1 for your reference:
| Pattern for General Case | Big-O | Description |
|---|---|---|
| \(T(n) = T(n / 2) + O(1) \) | \(O(\log n)\) |
Function does constant work and makes a single recursive call on half the input.
|
| \(T(n) = T(n - 1) + O(1) \) | \(O(n)\) |
Function does constant work and makes a single recursive call on input reduced by one.
|
| \(T(n) = 2 \cdot T(n / 2) + O(n) \) | \(O(n \log n)\) |
Function does linear work and makes two recursive calls on half the input.
|
Subsection 25.14.2 Vocabulary
- Big-O notation
-
A mathematical notation used to describe the efficiency of algorithms in terms of how their resource usage grows as the size of the input grows.
- linear complexity
-
An algorithm where the growth rate is \(O(n)\text{,}\) meaning that the time taken grows as a linear function of the size of the input.
- logarithmic complexity
-
An algorithm where the growth rate is \(O(\log n)\text{,}\) meaning that the time taken grows as a logarithmic function of the size of the input.
- log-linear complexity
-
An algorithm where the growth rate is \(O(n \log n)\text{,}\) meaning that the time taken grows as a log-linear function of the size of the input.
- quadratic complexity
-
An algorithm where the growth rate is \(O(n^2)\text{,}\) meaning that the time taken grows as a quadratic function of the size of the input.
- time complexity
-
A measure of the amount of time an algorithm takes to complete as a function of the size of its input. This complexity is analyzed in terms of the number of basic operations performed by the algorithm.
- wall time
-
The actual time taken from the start to the end of a program’s execution, as would be measured by a clock on the wall. Also called wall-clock time.
You have attempted of activities on this page.
