Algorithm analysis is dealt with the execution or running time of various operations involved. Running time of an operation can be defined as number of computer instructions executed per operation. The time complexity of an algorithm is commonly expressed using asymptotic notations known as Big O – (O), Big Theta – (Θ), Big Omega (Ω)
Space Complexity of an algorithm denotes the total space used or needed by the algorithm for its working, for various input sizes
Time complexity is the number of operations an algorithm performs to complete its task with respect to input size
Asymptotic Notation identifies the behavior of an algorithm as the input size changes. In this analysis, we treat algorithm as a function(f) with input size(n) and f(n) being the running time. This can be represented by a graph where the Y-axis is the runtime, the X-axis is the input size, and plot points are the resultants of the amount of time for a given input size.
Interested to read more ….click ..Analyzing Algorithms [download text]
Understanding Time Complexity
The running time of a program, also known as the execution time or time complexity, refers to the amount of time it takes for a program to execute or complete its tasks. It is typically measured in units of time, such as seconds or milliseconds.
The running time of a program depends on various factors, including the algorithm used, the input size, the hardware on which it is executed, and the efficiency of the implementation. It is often analyzed using Big O notation, which provides an upper bound on the growth rate of the running time as the input size increases.
The running time of a program can be classified into different categories:
- Constant Time (O(1)): The running time remains constant regardless of the input size. This means that the program takes the same amount of time to execute, regardless of how large the input is.
- Linear Time (O(n)): The running time increases linearly with the input size. For example, if the input size is doubled, the running time will also roughly double.
- Logarithmic Time (O(log n)): The running time increases logarithmically with the input size. Algorithms with logarithmic time complexity are generally considered efficient, as they can handle large inputs relatively quickly.
- Quadratic Time (O(n^2)): The running time increases quadratically with the input size. This means that if the input size is doubled, the running time will roughly quadruple.
- Exponential Time (O(2^n)): The running time grows exponentially with the input size. Algorithms with exponential time complexity are generally considered inefficient and can become impractical for even moderately large inputs.
It’s important to note that the running time can vary based on different scenarios and implementations. Analyzing and understanding the time complexity of a program helps in assessing its efficiency and making informed decisions regarding algorithmic optimizations and scalability.
Understanding Space Complexity
The space complexity of a code refers to the amount of memory or storage space required by a program to run and store data during its execution. It measures the maximum amount of memory space used by the program as a function of the input size. Similar to time complexity, space complexity is often analyzed using Big O notation, which provides an upper bound on the growth rate of the space requirements.
Here are some common categories used to describe space complexity:
- Constant Space (O(1)): The space requirements of the program remain constant, regardless of the input size. It means that the program uses a fixed amount of memory throughout its execution.
- Linear Space (O(n)): The space requirements increase linearly with the input size. If the input size is doubled, the program will require approximately double the memory space.
- Quadratic Space (O(n^2)): The space requirements increase quadratically with the input size. If the input size is doubled, the program will require roughly four times the memory space.
- Logarithmic Space (O(log n)): The space requirements increase logarithmically with the input size. These algorithms are considered space-efficient, as they use a minimal amount of memory even for large inputs.
- Exponential Space (O(2^n)): The space requirements grow exponentially with the input size. These algorithms are generally considered inefficient in terms of space usage and can quickly consume large amounts of memory, making them impractical for larger inputs.
It’s important to note that space complexity analysis considers only the additional space used by the program, excluding the space required to store the input itself. In some cases, a program may have both time and space complexity, and it’s important to optimize both aspects to ensure efficient execution and resource usage.
Lets explore the following videos to develop good understanding of ALGORITHMS ANALYSIS. [Click the following links to watch the video]
- Basics of Asymptotic Notations [read text]
- Analyzing Running Time of Iterative Program Code [read text]
- Analyzing Running Time of Recursive Code using Back Substitution method [read text]
- Analyzing Running Time of Recursive Code using Recursive tree Method
- Analyzing Space Complexity
You are invited to raise queries by writing your question in the box given below
Expertvision 
Why the best case for insertion sort is O(n), not O(n^2)?
to answer this question i try to use this example
for (i=1; i0) && (s[j] < s[j-1])) {
swap(&s[j],&s[j-1]);
j = j-1;
}
}
The best case for any sorting algorithm is when input is already in sorted order. in this example, the condition at while loop always returns false and hence it only iterates for the outer for loop, doing the job in linear time with O(n) time complexity.
As Correctly mentioned by Akhror above, at each iteration of outer loop, inner loop will not execute. and thus the running time will be derived from the number of times the outer loop works. which is n-1 times . Hence 0(n)
O(n) is a requirement for Optimal Solutions when a Search for Unsorted Data is occured. Moreover, O(n^2) is considered as Worst-Case Complexity as when Elements are in Reversed Order. Futhermore, . The best case for any Sorting Algorithm is when Input is already in sorted order as in scenario for Insertion Sort O(n), elements are sorted in ascending order
In insertions sort, the best case occurs when the data structure is already sorted. Because current element is compared with previous element, they will be in correct positions and does not require any movement or comparisons. That is why after n(the size of data structure) iterations, it concludes it is sorted.
Good question,
The best case for this scenario is when array is sorted.
In this situation, only works the outer.
When one loop works n time, then it will be Theta(n)
What conclusion can we make about comparison of Logarithm of a with base b to that of k depending on Three Cases(a>b^k, a=b^k, a<b^k) of Master's Theorem to Forms of Recurrences whereas we have constants as (a, b, k) and a real number(p) ?
k is your answer. I mean when you find answer you k comes from your answer and Masters theorem and it should satisfy given conditions. Hope it can help.
These three cases will provide the classification of your recurrence relation and provide the running time of an algorithm
Which method is powerful to find O(n) in your opinion? Back Subtitution, Recursive Tree or Master’s Theorem?
depending where you use
Which method is powerful to find Cost of Algorithm* in your opinion? Back Subtitution, Recursive Tree or Master’s Theorem?
If you are good at math, you will find back substitution easier. However, if you will use tree method you can see the cost right immediately from tree and add them up or at least you can visualize how algorithm behaves.
Back Substitution method takes more times as compared to Tree method which directly illustrates the behavior and move to next level. Master theorem, even more faster that only requires mapping of your recurrence relation with the standard form and provide the result directly.
So, if we can’t find the solution by using one method, does it mean that there is no chanse to find it by using other methods?
If a given Recurrence relation is correct, then it can be found out by all methods
In master’s theorem for the case: T(n)=aT(n/b)+Theta(n^k*log(n)^p), what if the log term is not there in the exercise. What should we take as a value of p? p<-1?
If log term is not there, take p as zero.