For Logarithmic, this value is ignored. For Polynomial, enter $k > 0$. For Exponential, enter $c > 1$.
function compareGrowthRates() {
// 1. Get Inputs
var type1 = document.getElementById("seqType1").value;
var param1 = parseFloat(document.getElementById("seqParam1").value);
var type2 = document.getElementById("seqType2").value;
var param2 = parseFloat(document.getElementById("seqParam2").value);
var resultDiv = document.getElementById("growthResult");
resultDiv.style.display = "block";
// 2. Validation Logic
// Ensure parameters are numbers if required by the type
if (type1 !== 'log' && isNaN(param1)) {
resultDiv.innerHTML = "Error: Please enter a valid numerical parameter for Sequence 1.";
return;
}
if (type2 !== 'log' && isNaN(param2)) {
resultDiv.innerHTML = "Error: Please enter a valid numerical parameter for Sequence 2.";
return;
}
// Mathematical constraints check
if ((type1 === 'exp' && param1 <= 1)) {
resultDiv.innerHTML = "Error: For exponential growth ($c^n$), the base $c$ must be greater than 1 for Sequence 1.";
return;
}
if ((type2 === 'exp' && param2 <= 1)) {
resultDiv.innerHTML = "Error: For exponential growth ($c^n$), the base $c$ must be greater than 1 for Sequence 2.";
return;
}
if ((type1 === 'poly' && param1 <= 0)) {
resultDiv.innerHTML = "Error: For polynomial growth ($n^k$), the exponent $k$ must be positive for Sequence 1.";
return;
}
if ((type2 === 'poly' && param2 <= 0)) {
resultDiv.innerHTML = "Error: For polynomial growth ($n^k$), the exponent $k$ must be positive for Sequence 2.";
return;
}
// 3. Define Hierarchy & Compare
// Hierarchy rank: Log (1) < Poly (2) < Exp (3)
var hierarchy = { 'log': 1, 'poly': 2, 'exp': 3 };
var rank1 = hierarchy[type1];
var rank2 = hierarchy[type2];
var conclusionText = "";
var limitText = "";
if (rank1 rank2) {
// Sequence 1 is a faster category
conclusionText = "Sequence 1 ($a_n$) grows significantly faster than Sequence 2 ($b_n$).";
limitText = "The limit ratio $\\lim_{n \\to \\infty} \\frac{a_n}{b_n} = \\infty$. In asymptotic notation, $a_n \\in \\omega(b_n)$.";
} else {
// Same category, compare parameters
if (type1 === 'log') {
conclusionText = "Both sequences have the same asymptotic growth rate.";
limitText = "Logarithmic functions of different bases differ only by a constant factor. $\\lim_{n \\to \\infty} \\frac{a_n}{b_n} = constant > 0$. They are $\\Theta(\\log n)$.";
} else if (type1 === 'poly') {
// Compare exponents
if (param1 < param2) {
conclusionText = "Sequence 2 grows faster (higher degree polynomial).";
limitText = "Since exponent " + param1 + " param2) {
conclusionText = "Sequence 1 grows faster (higher degree polynomial).";
limitText = "Since exponent " + param1 + " > " + param2 + ", the limit ratio is $\\infty$. $n^{" + param1 + "} \\in \\omega(n^{" + param2 + "})$.";
} else {
conclusionText = "Both sequences have exactly the same growth rate.";
limitText = "The exponents are equal. The limit ratio is a constant. They are $\\Theta(n^{" + param1 + "})$.";
}
} else if (type1 === 'exp') {
// Compare bases
if (param1 < param2) {
conclusionText = "Sequence 2 grows faster (larger exponential base).";
limitText = "Since base " + param1 + " param2) {
conclusionText = "Sequence 1 grows faster (larger exponential base).";
limitText = "Since base " + param1 + " > " + param2 + ", the limit ratio is $\\infty$. $" + param1 + "^n \\in \\omega(" + param2 + "^n)$.";
} else {
conclusionText = "Both sequences have exactly the same growth rate.";
limitText = "The bases are equal. They are $\\Theta(" + param1 + "^n)$.";
}
}
}
// 4. Output Result
resultDiv.innerHTML = "
Comparison Results:
" + conclusionText + "" + limitText + "";
}
Understanding the Growth Rates of Sequences Theorem
In mathematics and computer science, particularly in algorithm analysis, understanding how rapidly a sequence grows as its index $n$ approaches infinity is crucial. The "Growth Rates of Sequences Theorem" provides a rigorous method for comparing the asymptotic behavior of two different sequences, often denoted as $a_n$ and $b_n$.
The Core Theorem Using Limits
To compare the growth rates of two sequences $a_n$ and $b_n$ (assuming they are positive for large $n$), we evaluate the limit of their ratio as $n$ goes to infinity:
$$ L = \lim_{n \to \infty} \frac{a_n}{b_n} $$
The outcome of this limit $L$ tells us their relative growth speeds:
If $L = 0$: Sequence $a_n$ grows strictly slower than $b_n$. In Big-O notation terms, $a_n \in o(b_n)$ (little-o).
If $L = \infty$: Sequence $a_n$ grows strictly faster than $b_n$. In notation, $a_n \in \omega(b_n)$ (little-omega).
If $L = c$ (where $c$ is a positive constant): Both sequences grow at the same asymptotic rate. They differ only by a constant factor. In notation, $a_n \in \Theta(b_n)$ (Big-Theta).
The Standard Hierarchy of Growth Rates
When analyzing algorithms, we often encounter standard classes of functions. Knowing the hierarchy defines which algorithms will perform better on large datasets. Listed from slowest growing to fastest growing:
Logarithmic ($\log n$): Grows very slowly. Doubling the input size only adds a constant amount to the sequence value.
Polynomial ($n^k$, e.g., $n$, $n^2$, $n^3$): Growth is determined by the exponent $k$. A higher exponent means significantly faster growth. $n^2$ always grows faster than $n^{1.99}$ eventually.
Exponential ($c^n$, where $c > 1$): Grows incredibly fast. Even a small base like $1.1^n$ will eventually dwarf any polynomial sequence like $n^{100}$.
Factorial ($n!$): Grows even faster than standard exponential functions (not included in the basic calculator above, but sits at the top of this common hierarchy).
Practical Example
Consider comparing an algorithm with a running time of $a_n = n^3$ versus one with $b_n = 2^n$. Using the calculator or the theorem:
$$\lim_{n \to \infty} \frac{n^3}{2^n} = 0$$
Because the limit is 0, we know that $2^n$ grows much faster than $n^3$. Therefore, for very large inputs, the $n^3$ algorithm is vastly more efficient.