DAA Assignment 1

Jul 29, 2025

Updated 1 day ago

2 min read

Algorithm Analysis: Comparing Growth Rates of n², nlog₂n, and 3ⁿ

In algorithm analysis, comparing the growth of functions like $n lo g_{2} n$ , $n^{2}$ , and $3^{n}$ helps us understand their time complexity and efficiency as input size increases. Among these, $n lo g_{2} n$ grows the slowest and is commonly seen in efficient algorithms like Merge Sort, while $n^{2}$ grows faster and appears in less efficient approaches such as simple nested loops. On the other hand, $3^{n}$ grows exponentially and increases extremely rapidly, making algorithms with this complexity impractical for even moderately large inputs. Therefore, in terms of growth rate, $n lo g_{2} n$ is the most efficient, followed by $n^{2}$ , and $3^{n}$ is the least efficient for large values of $n$ .

For a deeper understanding of how these functions are formally classified, refer to Asymptotic Notation and Comparison of Two Functions.

algorithm analysis : Growth Rates comparison of n², n log₂n, and 3ⁿ

Compare the Growth of the Functions $n^{2}$ , $n lo g_{2} n$ , and $3^{n}$

Case 1: Comparing $n^{2}$ vs $n lo g_{2} n$

Let:

$t (n) = n^{2}$
$g (n) = n lo g_{2} n$

n \to \infty lim \frac{t ( n )}{g ( n )} = n \to \infty lim \frac{n ^{2}}{n lo g _{2} n}

This is an $\frac{\infty}{\infty}$ form, so apply L'Hôpital's Rule.

Apply L'Hôpital's Rule

Differentiate the numerator:

t^{'} (n) = \frac{d}{d n} (n^{2}) = 2 n

Differentiate the denominator:

Using the product rule on $g (n) = n \cdot lo g_{2} n$ :

g^{'} (n) = lo g_{2} n \cdot \frac{d}{d n} (n) + n \cdot \frac{d}{d n} (lo g_{2} n) = lo g_{2} n + n \cdot \frac{1}{n ln 2} = lo g_{2} n + \frac{1}{ln 2}

\frac{t ^{'} ( n )}{g ^{'} ( n )} = \frac{2 n}{lo g _{2} n + \frac{1}{l n 2}}

n \to \infty lim \frac{t ^{'} ( n )}{g ^{'} ( n )} = \frac{\infty}{\infty}

Apply L'Hôpital's Rule Again

t^{''} (n) = \frac{d}{d n} (2 n) = 2

g^{''} (n) = \frac{d}{d n} (lo g_{2} n + \frac{1}{ln 2}) = \frac{d}{d n} lo g_{2} n + 0 = \frac{1}{n ln 2}

\frac{t ^{''} ( n )}{g ^{''} ( n )} = \frac{2}{\frac{1}{n l n 2}} = 2 n ln 2

n \to \infty lim 2 n ln 2 = \infty

\infty implies t (n) has a larger order of growth than g (n)

n^{2} > n lo g_{2} n

Case 2: Comparing $n^{2}$ vs $3^{n}$

Let:

$t (n) = n^{2}$
$g (n) = 3^{n}$

n \to \infty lim \frac{t ( n )}{g ( n )} = n \to \infty lim \frac{n ^{2}}{3 ^{n}}

This is an $\frac{\infty}{\infty}$ form, so apply L'Hôpital's Rule.

Apply L'Hôpital's Rule

Differentiate the numerator:

t^{'} (n) = \frac{d}{d n} (n^{2}) = 2 n

Differentiate the denominator:

g^{'} (n) = \frac{d}{d n} (3^{n}) = 3^{n} ln 3

\frac{t ^{'} ( n )}{g ^{'} ( n )} = \frac{2 n}{3 ^{n} ln 3}

n \to \infty lim \frac{2 n}{3 ^{n} ln 3} = \frac{\infty}{\infty}

Apply L'Hôpital's Rule Again

t^{''} (n) = \frac{d}{d n} (2 n) = 2

g^{''} (n) = \frac{d}{d n} (3^{n} ln 3) = ln 3 \cdot \frac{d}{d n} (3^{n}) = ln 3 \cdot 3^{n} \cdot ln 3 = (ln 3)^{2} \cdot 3^{n}

\frac{t ^{''} ( n )}{g ^{''} ( n )} = \frac{2}{( ln 3 ) ^{2} \cdot 3 ^{n}}

n \to \infty lim \frac{2}{( ln 3 ) ^{2} \cdot 3 ^{n}} = \frac{2}{\infty} = 0

0 implies t (n) has a smaller order of growth than g (n)

n^{2} < 3^{n}

Result

Function	Order of Growth
$3^{n}$	Highest
$n^{2}$	2nd Highest
$n lo g_{2} n$	Smallest (Most Efficient)

This ranking directly aligns with the principles of asymptotic analysis. Algorithms with $n lo g_{2} n$ complexity, such as Merge Sort and Quick Sort, are significantly more scalable than those with $n^{2}$ or exponential time complexity. Understanding these differences is foundational to the Design and Analysis of Algorithms.

For practice with related concepts, see DAA Previous Year Questions and Binary Search Recurrence Relation.

For an authoritative reference on algorithm complexity, see the Big-O Cheat Sheet and Khan Academy's explanation of asymptotic notation.

DAA Assignment 1

Algorithm Analysis: Comparing Growth Rates of n², nlog₂n, and 3ⁿ

Compare the Growth of the Functions n2, nlog2​n, and 3n

Case 1: Comparing n2 vs nlog2​n

Apply L'Hôpital's Rule

Apply L'Hôpital's Rule Again

Case 2: Comparing n2 vs 3n

Apply L'Hôpital's Rule

Apply L'Hôpital's Rule Again

Result

Compare the Growth of the Functions $n^{2}$ , $n lo g_{2} n$ , and $3^{n}$

Case 1: Comparing $n^{2}$ vs $n lo g_{2} n$

Case 2: Comparing $n^{2}$ vs $3^{n}$