Basics of Asymptotic Analysis (Part 3)

Basics of Asymptotic Analysis - Part 3

In this section, we learn that examining the exact running time of an algorithm is not practical. The running time generally depends on the size of the input, and we need to consider the growth rate of the function representing the number of instructions executed for a given input value.

Running Time Depends on Input Size

• Measuring the actual running time is not practical.

• The running time generally depends on the size of the input.

• Adding an element to an array requires shifting elements, which becomes more costly as the array size increases.

Time Complexity and Function FN

• The time complexity, denoted by FN, represents the number of instructions executed for a given input value.

• FN is a function that depends on the input size (n).

• We are interested in comparing different data structures or algorithms based on their growth rate (FN) with respect to n.

Finding Growth Rate (FN)

• Finding FN in small programs is easy, but it becomes challenging in complex programs.

• We compare two data structures or algorithms by comparing their FN values.

• We are interested in understanding how FN grows as n increases.

Example Calculation

• Given FN = 5n^2 + 6n + 12 as a representation of time or number of instructions executed for input value n.

• Calculate percentages for each term's contribution to total running time at n = 1:

• Percentage due to 5n^2:

• Percentage due to 6n:

• Percentage due to 12:

It is important to analyze and compare growth rates rather than focusing solely on smaller input sizes.

New Section

This section discusses the time complexity of different terms in a growth function as the value of 'n' increases.

Analysis of Time Complexity

• The percentage contribution of each term in the growth function decreases as 'n' increases.

• For smaller values of 'n', the squared term consumes most of the time.

• As 'n' increases, the squared term continues to dominate, while other terms become negligible.

• Visualizing the growth rate shows that the squared term takes up most of the time.

• Eliminating less significant terms does not affect the overall approximate time complexity.

New Section

This section explains why we focus on calculating approximate time complexity and introduces asymptotic complexity.

Approximate Time Complexity

• Calculating exact running time is not necessary; instead, we focus on an approximate measure called asymptotic complexity.

• Asymptotic complexity eliminates unnecessary terms and concentrates on the term that consumes most of the time.

• We are interested in calculating an approximate measure of time complexity rather than exact running times or specific machine execution details.

New Section

This section emphasizes that time complexity depends on input size and concludes our satisfaction with obtaining an approximate measure.

Conclusion and Input Size Dependency

• Time complexity depends on input size; increasing input size affects time consumption.

• We are satisfied with obtaining an approximate measure of time complexity without considering exact running times or machine specifics.