Computational Complexity is a rough sense of how much computing resources will be required for an algorithm to handle input data of various sizes or values, particularly in terms of time and space (memory or storage.)
• Algorithm Complexity is essentially a synonym for Computational Complexity.
• It primarily focuses on analyzing the efficiency of algorithms in terms of their time and space usage.
Major aspects of Computational Complexity:
1.) Time Complexity:
Time complexity measures the amount of time an algorithm takes to complete its execution as a function of the size of its input. It provides an estimate of how the runtime of an algorithm grows with the size of the problem.
• It is typically expressed using Big O notation (O()), which describes the upper bound on the growth rate of an algorithm’s runtime.
• Common time complexities include O(1) (constant time), O(log n) (logarithmic time), O(n) (linear time), O(n log n) (linearithmic time), O(n^2) (quadratic time), O(2^n) (exponential time), etc.
• Analyzing the time complexity helps determine how efficiently an algorithm scales with larger inputs and enables comparison between different algorithms for solving the same problem.
2.) Space Complexity:
Space complexity measures the amount of memory (or space) an algorithm requires to solve a problem as a function of the size of its input. It provides an estimate of how the memory usage of an algorithm grows with the size of the problem.
• Space complexity is also expressed using Big O notation (O()), which describes the upper bound on the growth rate of an algorithm’s memory usage.
• Common space complexities include O(1) (constant space), O(n) (linear space), O(n^2) (quadratic space), etc.
• Analyzing the space complexity helps determine the memory requirements of an algorithm and assess its scalability with larger inputs.
