Page 27 - DCAP407_DATA_STRUCTURE

Data Structure

2. Space Complexity: It is a function that describes the amount of memory or space required by an
algorithm to run. A good algorithm has minimum number of space complexity.
Algorithm analysis is an important part of computational complexity theory. It provides theoretical
estimates for the resources that are needed for any algorithm to solve a given problem. These estimates
provide an insight into the measures that determine algorithm efficiency. It is necessary to check the
efficiency of each of the algorithms in order to select the best algorithm. We can easily measure the
efficiency of algorithms by calculating their time complexity. The shorthand way to represent time
complexity is asymptotic notation.

Consider the algorithm for sorting a deck of cards. This algorithm continues by
repeatedly searching through the deck for the lowest card. The square of the
number of cards in the deck is the asymptotic complexity of this algorithm.
2.1 Mathematical Notation and Functions
Algorithms are widely used in various areas of study. We can solve different problems using the same
algorithm. Therefore, all algorithms must follow a standard. The mathematical notations use symbols or
symbolic expressions, which have a precise semantic meaning.
According to Lancelot Hogben, "Every meaningful mathematical statement can also be expressed in
plain language. Many plain language statements of mathematical expressions would fill several pages,
while to express them in mathematical notation might take as little as one line. One of the ways to
achieve this remarkable compression is to use symbols to stand for statements, instructions, and so on."
2.1.1 Asymptotic Notations
A problem may have various algorithmic solutions. In order to choose the best algorithm for a
particular process, you must be able to judge the time taken to run a particular solution. More
accurately, you must be able to judge the time taken to run two solutions, and choose the better among
the two.
To select the best algorithm, it is necessary to check the efficiency of each algorithm. The efficiency of
each algorithm can be checked by computing its time complexity. The asymptotic notations help to
represent the time complexity in a shorthand way. It can generally be represented as the fastest
possible, slowest possible or average possible.
Asymptotic notation within the limit deals with the character of a function that is a parameter with
large values. The main characteristic of this approach is that, importance is given to the terms while
neglecting the constant factors present in the expression. This helps in the classification of run-time
functions into broad efficiency classes.
The notations such as O (Big-O), Ώ (Omega), and θ (Theta) are called as asymptotic notations. These are
the mathematical notations that are used in three different cases of time complexity.

Big-O Notation
‘O’ is the representation for Big-O notation. Big-O is the method used to express the upper bound of the
running time of an algorithm. It is used to describe the performance or time complexity of the
algorithm. Big-O specifically describes the worst-case scenario and can be used to describe the execution
time required or the space used by the algorithm.

20 LOVELY PROFESSIONAL UNIVERSITY