How to study efficiency of algorithms?
The way to study the efficiency of an algorithm is to implement it and experiment by running the program on various test inputs while recording the time spent during each execution. A simple mechanism in Java is based on use of the currentTimeMillis() method of the System class for collecting such running times. That method reports the number of milliseconds that have passed since a benchmark time known
as the epoch (January 1, 1970 UTC).The key is that if we record the time immediately before executing the algorithm and then immediately after it.
long start = System.currentTimeMillis( ); // record the starting time
/? (run the algorithm) ?/
long end = System.currentTimeMillis( ); // record the ending time
long elapsed = end ? start; //Total time elapsed
Measuring elapsed time provides a reasonable reflection of an algorithm’s efficiency.
Asymptotic Notation and Analysis (Based on input size) in Complexity Analysis of Algorithms
Asymptotic Analysis is defined as the big idea that handles the above issues in analyzing algorithms. In Asymptotic Analysis, we evaluate the performance of an algorithm in terms of input size (we don’t measure the actual running time). We calculate, how the time (or space) taken by an algorithm increases with the input size.
Asymptotic notation is a way to describe the running time or space complexity of an algorithm based on the input size. It is commonly used in complexity analysis to describe how an algorithm performs as the size of the input grows. The three most commonly used notations are Big O, Omega, and Theta.
- Big O notation (O): This notation provides an upper bound on the growth rate of an algorithm’s running time or space usage. It represents the worst-case scenario, i.e., the maximum amount of time or space an algorithm may need to solve a problem. For example, if an algorithm’s running time is O(n), then it means that the running time of the algorithm increases linearly with the input size n or less.
- Omega notation (?): This notation provides a lower bound on the growth rate of an algorithm’s running time or space usage. It represents the best-case scenario, i.e., the minimum amount of time or space an algorithm may need to solve a problem. For example, if an algorithm’s running time is ?(n), then it means that the running time of the algorithm increases linearly with the input size n or more.
- Theta notation (?): This notation provides both an upper and lower bound on the growth rate of an algorithm’s running time or space usage. It represents the average-case scenario, i.e., the amount of time or space an algorithm typically needs to solve a problem. For example, if an algorithm’s running time is ?(n), then it means that the running time of the algorithm increases linearly with the input size n.
In general, the choice of asymptotic notation depends on the problem and the specific algorithm used to solve it. It is important to note that asymptotic notation does not provide an exact running time or space usage for an algorithm, but rather a description of how the algorithm scales with respect to input size. It is a useful tool for comparing the efficiency of different algorithms and for predicting how they will perform on large input sizes.