Time Complexity in Data Structure

Introduction:

Time complexity is a critical concept in computer science and plays a vital role in the design and analysis of efficient algorithms and data structures. It allows us to measure the amount of time an algorithm or data structure takes to execute, which is crucial for understanding its efficiency and scalability.

What is Time Complexity:

Time complexity measures how many operations an algorithm completes in relation to the size of the input. It aids in our analysis of the algorithm's performance scaling with increasing input size. Big O notation (O()) is the notation that is most frequently used to indicate temporal complexity. It offers an upper bound on how quickly an algorithm's execution time will increase.

Best, Worst, and Average Case Complexity:

In analyzing algorithms, we consider three types of time complexity:

1. Best-case complexity (O(best)): This represents the minimum time required for an algorithm to complete when given the optimal input. It denotes an algorithm operating at its peak efficiency under ideal circumstances.
2. Worst-case complexity (O(worst)): This denotes the maximum time an algorithm will take to finish for any given input. It represents the scenario where the algorithm encounters the most unfavourable input.
3. Average-case complexity (O(average)): This estimates the typical running time of an algorithm when averaged over all possible inputs. It provides a more realistic evaluation of an algorithm's performance.

Big O Notation:

Time complexity is frequently expressed using Big O notation. It represents the maximum possible running time for an algorithm given the input size. Let's go through some crucial notations.:

a) O(1) - Constant Time Complexity:

If an algorithm takes the same amount of time to execute no matter how big the input is, it is said to have constant time complexity. This is the best case scenario as it shows how effective the algorithm is. Examples of operations having constant time complexity include accessing a component of an array or executing simple arithmetic calculations.

1. int?constantTimeExample(int?arr[],?int?size)?{??
2. ????return?arr[0];??
3. }??

As only one operation is required to return the first element of the array, the getFirstElement function has an O(1) time complexity.

b) O(log n) - Logarithmic Time Complexity:

According to logarithmic time complexity, the execution time increases logarithmically as the input size increases. Algorithms with this complexity are often associated with efficient searching or dividing problems in half at each step. A well-known illustration of an algorithm having logarithmic time complexity is the binary search.

1. int?binarySearch(int?arr[],?int?size,?int?target)?{??
2. ??
3. ??
4. ????int?low?=?0;??
5. ????int?high?=?size?-?1;??
6. ??
7. ??
8. ????while?(low?<=?high)?{??
9. ????????int?mid?=?(low?+?high)?/?2;??
10. ??
11. ????????if?(arr[mid]?==?target)??
12. ????????????return?mid;??
13. ????????else?if?(arr[mid]?<?target)??
14. ????????????low?=?mid?+?1;??
15. ????????else??
16. ????????????high?=?mid?-?1;??
17. ????}??
18. ??
19. ????return?-1;?//?Not?found??
20. }??

The binarySearch function has a time complexity of O(log n) as it continuously halves the search space until it finds the target element or determines its absence.

c) O(n) - Linear Time Complexity:

According to linear time complexity, the running time grows linearly with the size of the input. When navigating data structures or performing actions on each piece, it is frequently noticed. For example, traversing an array or linked list to find a specific element.

1. int?linearTimeExample(int?arr[],?int?size)?{??
2. ????int?sum?=?0;??
3. ??
4. ??
5. ????for?(int?i?=?0;?i?<?size;?i++)?{??
6. ????????sum?+=?arr[i];??
7. ????}??
8. ??
9. ????return?sum;??
10. }??

The printArray function has a time complexity of O(n) as it iterates over each element in the array to print its value.

d) O(n^2) - Quadratic Time Complexity:

An algorithm whose runtime quadratically increases with input size. O(n^2) denotes quadratic time complexity, in which an algorithm's execution time scales quadratically with the amount of the input. This type of time complexity is often observed in algorithms that involve nested iterations or comparisons between multiple elements.

1. void?printPairs(int?arr[],?int?size)?{??
2. ????for?(int?i?=?0;?i?<?size;?i++)?{??
3. ????????for?(int?j?=?0;?j?<?size;?j++)?{??
4. ????????????cout?<<?"("?<<?arr[i]?<<?",?"?<<?arr[j]?<<?")?";??
5. ????????}??
6. ????}??
7. }??

The printPairs function has a time complexity of O(n^2) as it performs nested iterations over the array, resulting in a quadratic relationship between the execution time and the input size.

e) O(2^n) - Exponential Time Complexity:

An algorithm that exhibits an exponential relationship between the execution time and the input size. Exponential time complexity indicates that the algorithm's execution time doubles with each additional element in the input, making it highly inefficient for larger input sizes. This type of time complexity is often observed in algorithms that involve an exhaustive search or generate all possible combinations.

1. int?fibonacci(int?n)?{??
2. ????if?(n?<=?1)??
3. ????????return?n;??
4. ????return?fibonacci(n?-?1)?+?fibonacci(n?-?2);??
5. }??

The Fibonacci function has a time complexity of O(2^n) as it recursively calculates the Fibonacci sequence, resulting in an exponential increase in the execution time as the input size increases.

f) O(n!) - Factorial Time Complexity:

An algorithm whose runtime increases proportionally to the size of the input. This kind of time complexity is frequently seen in algorithms that generate every combination or permutation of a set of components.

1. void?permute(string?str,?int?l,?int?r)?{??
2. ????if?(l?==?r)?{??
3. ??
4. ????????cout?<<?str?<<?"?";??
5. ????????return;??
6. ????}??
7. ????for?(int?i?=?l;?i?<=?r;?i++)?{??
8. ????????swap(str[l],?str[i]);??
9. ????????permute(str,?l?+?1,?r);??
10. ????????swap(str[l],?str[i]);??
11. ????}??
12. }??

The permute function has a time complexity of O(n!) as it generates all possible permutations of a given string, resulting in a factorial increase in the execution time as the input size increases.

How to Calculate Time Complexity?

Analysing the growth rate of an algorithm's running time as input size grows is necessary to determine how time-complex it is. It gives an estimate of how the algorithm performs as the input size increases. Here are the general steps to calculate time complexity:

• Identify the algorithm: Determine the specific algorithm or code snippet for which you want to calculate the time complexity. It could consist of a series of operations combined with a loop or a recursive function.
• Identify the input size: Identify the elements that make up the algorithm's input size. For example, if the algorithm operates on an array, the input size could be the length of the array.
• Determine the basic operations: Identify the fundamental operations that contribute to the running time of the algorithm. These operations could be comparisons, assignments, arithmetic operations, function calls, or any other significant actions.
• Count the operations: Analyze how many times each basic operation is executed as a function of the input size. You may need to consider different scenarios or branches within the algorithm.
• Express the count as a function of the input size: Create a mathematical expression that represents the count of basic operations as a function of the input size. It ought to outline the worst-case scenario or the performance limit of the algorithm.
• Simplify the expression: Simplify the mathematical expression by removing constants, lower-order terms, and insignificant factors. Focus on the most dominant term that represents the growth rate of the algorithm.
• Determine the time complexity notation: Use Big O notation to express the condensed expression, where Big O indicates the time complexity's upper bound. O(1) stands for constant time, O(n) for linear time, O(n^2) for quadratic time, and so forth are common notations.

HAPPY LEARNING!!! HAPPY CODING!!!