What do you mean by the complexity of an algorithm? Explain the asymptotic notations used to describe the time/space complexity of any algorithm with their geometrical interpretation and example.

Question

Suresh Chand · Accepted Answer

The complexity of an algorithm defines the performance of the algorithm in terms of the input size. We consider the complexities of every algorithm and compare them while choosing the most efficient algorithm to solve our problem. There are 2 types of complexity to consider for an algorithm Time Complexity Space Complexity Time Complexity: The time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input. Note that the time to run is a function of the length of the input and not the actual execution time of the machine on which the algorithm is running. Space Complexity: The space complexity of an algorithm quantifies the amount of space taken by an algorithm to run as a function of the length of the input. Asymptotic notation is used to describe the time/space complexity of an algorithm: Whenever we want to perform an analysis of an algorithm, we need to calculate the complexity of that algorithm. It does not provide the exact amount of resources required. so instead of taking the exact amount of resources, we represent that complexity in a general form which produces the basic nature of that algorithm. We use that general form for the analysis process. Complexity analysis of an algorithm is very hard if we try to analyze it exactly. We know that the complexity (worst, best, or average) of an algorithm is the mathematical function of the size of the input. So if we analyze the algorithm in terms of bound (upper and lower) then it would be easier. For this purpose, we need the concept of asymptotic notations. Asymptotic notation is a way of comparing functions that ignores constant factors and small input sizes. These notations are used to calculate the running time complexity of the algorithm. Big Oh Notation (O): Big-Oh notation is used to define the upper bound of an algorithm in terms of Time Complexity. It always indicates the maximum time required by an algorithm for all input values. It describes the worst case of an algorithm time complexity. In the above graph after a particular input value n0, always C g(n) is greater than f(n) which indicates the algorithm's upper bound. Example: Find Big oh of the given function f(n) = 3n2 + 4n + 7 solution: We have f(n) = 3n2 + 4n + 7 <= 3n2 + 4n2+7n2 <= 14n2 f(n) <= 14n2 where c = 14 and g(n) = n2, thus f(n) = O(g(n)) = O(n2) Big - Omege Notation (Ω): Big-Omega notation is used to define the lower bound of an algorithm in terms of Time Complexity. It always indicates the minimum time required by an algorithm for all input values. It describes the best case of an algorithm time complexity. In the above graph after a particular input value n0, always C g(n) is less than f(n) which indicates the algorithm's lower bound. Example: Find Big oh of the given function f(n) = 3n2 + 4n + 7 Solution: we have f(n) = 3n2 + 4n + 7 >= 3n2 f(n) = 3n2 where c = 14 and g(n) = n2, thus f(n) = Ω(g(n)) = Ω(n2) Big-Theta Notation (Θ): Big-Theta notation is used to define the average bound of an algorithm in terms of Time Complexity. It indicates the average time required by an algorithm for all input values. It describes the average case of an algorithm time complexity. In the above graph after a particular input value n0, always C1 g(n) is less than f(n) and C2 g(n) is greater than f(n) which indicates the algorithm's average bound. Example: If f(n) = 3n2 + 4n + 7 g(n) = n2, then prove that f(n) = Θ(g(n)) proof: Let us consider c1, c2, and n0 values as 14, 1, and 1 respectively then we can have, f(n) <= c1 * g(n), n >= n0 as 3n2 + 4n + 7 <= 14n2, and f(n) <= c2 * g(n), n >= n0 as 3n2 + 4n + 7 <= 1n2, and For all n >= 1 (in both cases) so, c2 *g(n) <= f(n) <= c1 * g(n) is trival Hence, f(n) = Θ(g(n))

What do you mean by the complexity of an algorithm? Explain the asymptotic notations used to describe the time/space complexity of any algorithm with their geometrical interpretation and example.

Leave your Answer:

Hits Counter

Question

What do you mean by the complexity of an algorithm? Explain the asymptotic notations used to describe the time/space complexity of any algorithm with their geometrical interpretation and example.

Leave your Answer: