UNIT I ROLE OF ALGORITHMS IN COMPUTING & COMPLEXITY
ANALYSIS
Algorithms – Algorithms as a Technology – Time and Space complexity of
algorithms – Asymptotic analysis – Average and worst-case analysis – Asymptotic notation
– Importance of efficient algorithms – Program performance measurement – Recurrences:
The Substitution Method – The Recursion – Tree Method – Data structures and algorithms.
IMPORTANCE OF EFFICIENT ALGORITHMS
In computer science, algorithmic efficiency is a characteristic of an algorithm that
is related to the number of computational resources required by the algorithm. An
algorithm’s resource use must be evaluated, and the efficiency of an algorithm may be
assessed based on the use of various resources. For a recurring or continuous process,
algorithmic efficiency is comparable to engineering performance. We want to use as few
resources as possible to maximize efficiency. However, because various resources, such as
time and space complexity, cannot be directly compared, which of the proposed algorithms
is judged to be more efficient typically relies on whatever efficiency metric is considered
more significant.
Efficiency Factors
Efficiency is dependent on two factors:
Space Efficiency
In some cases, the amount of space/memory consumed has to be examined. For
example, in dealing with huge amounts of data or in programming embedded systems,
memory consumed must be analyzed.
Space/memory usage components are:
● Space of Instruction: Compiler, compiler settings, and target machine (CPU), all
have an impact on space of instruction.
MC4101 - ADVANCED DATA STRUCTURES AND ALGORITHMS
● Data Space: Data size/dynamically allocated memory, static program variables are all
factors affecting data space.
● Stack Space at Runtime: Compiler, run-time function calls and recursion, local
variables, and arguments all have an impact on stack space at runtime.
Time Efficiency
Obviously, the faster a program/function completes its objective, the better the
algorithm. The actual running time is determined by a number of factors:
● Computer’s Speed: processor (not simply clock speed), I/O, and so on.
● Compiler: The compiler, as well as the compiler parameters.
● Amount of Data: The amount of data, for example, whether to search a lengthy or
a short list.
● Actual Data: The actual data, such as whether the name is first or last in a sequential
search.
Approaches to Time Efficiency
MC4101 - ADVANCED DATA STRUCTURES AND ALGORITHMS
There are two ways to assess time complexity:
Asymptotic Categorization:
This employs basic categories to offer a basic notion of performance, which is
also called an order of magnitude. If the algorithms are similar, the data amount is little,
or performance is essential, then the next method can be explored further. Estimation of
running time depends on two things, i.e., Code Analysis and Code Execution, which are
elaborated below:
1. Code Analysis: We can accomplish the following things by analyzing the code:
● Operation Counts: Choose the most frequently performed operation(s) and count
how many times each one is performed.
● Step Counts: Calculate the total number of steps and potentially lines of code that
program executes.
2. Code Execution: We may accomplish the following by executing the code:
MC4101 - ADVANCED DATA STRUCTURES AND ALGORITHMS
● Benchmarking: Running the software on a variety of data sets and comparing the
results.
● Description: A report on the number of hours spent in each routine of a program,
which is used to identify and eliminate the program’s hot spots. This perception is
frequently questioned. Although other description modes give data in units other
than time (for example, call counts) and/or at levels of granularity besides per-
routine, the concept is the same.
Three Cases of Time Efficiency
● Worst case
● Average case
● Best case
The worst-case scenario is evaluated since it provides an upper limit on projected
performance. Furthermore, the average scenario is typically more difficult to establish
(it is more data dependent), and it is frequently the same as the worst case. It may be
essential to examine all three situations on some occasions.
MC4101 - ADVANCED DATA STRUCTURES AND ALGORITHMS