Space Complexity

Usually the term Space Complexity is misused for Auxiliary Space.

Following are the correct definitions of Auxiliary Space and Space Complexity.

Auxiliary Space is the temporary space used by an algorithm.

Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size.

Space complexity includes both Auxiliary space and space used by input.

Example:
While comparing sorting algorithms on the basis of space, Auxiliary Space would be a better choice than Space Complexity.

Analysis of Loops - Calculating Time Complexity

1) O(1): Time complexity of a function is considered as O(1) if it doesn’t contain loop, recursion and call to any other non-constant time function.

swap() function or loop or recursion that runs a constant number of timeshas O(1) time complexity.

Example:

for (int i = 1; i <= c; i++) {  // Here c is a constant   
        // some expressions
 }


2) O(n): Time Complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a constant amount.

Example:

for (int i = 1; i <= n; i += c) {   // Here c is a constant  
        // some expressions
}


3) O(n2) : Time complexity of nested loops is equal to the number of times the innermost statement is executed. Selection sort and Insertion Sort have O(n2)  time complexity.

Example:

for (int i = 1; i <=n; i += c) {
       for (int j = 1; j <=n; j += c) {
          // some expressions
       }
 }



4) O(Logn): Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a constant amount. Binary Search has O(Logn) time complexity.

for (int i = 1; i <=n; i *= c) {
       // some expressions
}



5) O(LogLogn): Time Complexity of a loop is considered as O(LogLogn) if the loop variables is reduced / increased exponentially by a constant amount.
 
for (int i = 2; i <=n; i = pow(i, c)) {  // Here c is a constant greater than 1   
       // some O(1) expressions
}
 

How to combine time complexities of consecutive loops?
When there are consecutive loops, we calculate time complexity as sum of time complexities of individual loops.

for (int i = 1; i <=m; i += c) {  
        // some expressions
}

for (int i = 1; i <=n; i += c) {
        // some expressions
}

Time complexity of above code is O(m) + O(n) which is O(m+n)
If m == n, the time complexity becomes O(2n) which is O(n).  


How to calculate time complexity when there are many if, else statements inside loops?
Worst case time complexity is the most useful among best, average and worst. Therefore we need to consider worst case.

We evaluate the situation when values in if-else conditions cause maximum number of statements to be executed.

For example consider the linear search function where we consider the case when element is present at the end or not present at all.

When the code is too complex to consider all if-else cases, we can get an upper bound by ignoring if else and other complex control statements.

Asymptotic Notations - Theta , Big O and Omega

Asymptotic notations are mathematical tools to represent time complexity of algorithms for asymptotic analysis.

The following 3 asymptotic notations are mostly used to represent time complexity of algorithms.


1) Θ Notation: The theta notation bounds a functions from above and below, so it defines exact asymptotic behavior.

A simple way to get Theta notation of an expression is to drop low order terms and ignore leading constants.

Example:
3n3 + 6n2 + 6000 = Θ(n3)

Dropping lower order terms is always fine because there will always be a n0 after which Θ(n3) beats Θn2) irrespective of the constants involved.



2) Big O Notation: The Big O notation defines an upper bound of an algorithm, it bounds a function only from above.

Example: Consider the case of Insertion Sort.

It takes linear time in best case and quadratic time in worst case. We can safely say that the time complexity of Insertion sort is O(n^2).

If we use Θ notation to represent time complexity of Insertion sort, we have to use two statements for best and worst cases:
1. Worst case time complexity = Θ(n^2).
2. Best case time complexity = Θ(n).

The Big O notation is useful when we only have upper bound on time complexity of an algorithm. Many times we easily find an upper bound by simply looking at the algorithm.



3) Ω Notation: Just as Big O notation provides an asymptotic upper bound on a function, Ω notation provides an asymptotic lower bound.

Ω Notation can be useful when we have lower bound on time complexity of an algorithm.

The best case performance of an algorithm is generally not useful, the Omega notation is the least used notation among all three.

Example: Consider the case of Insertion Sort.

The time complexity of Insertion Sort can be written as Ω(n), but it is not a very useful information about insertion sort, as we are generally interested in worst case and sometimes in average case.

Worst, Average and Best Case in Algorithms

Lets take an example of Linear Search and analyze it using Asymptotic analysis.

We can have three cases to analyze an algorithm:
1) Worst Case
2) Average Case
3) Best Case


Worst Case Analysis (Usually Done)
In this, we calculate upper bound on running time of an algorithm. We must know the case that causes maximum number of operations to be executed. For Linear Search, the worst case happens when the element to be searched is not present in the array. When the element is not present, search() functions compares it with all the elements of array one by one.

Therefore, the worst case time complexity of linear search would be Θ(n).


Average Case Analysis (Sometimes done) 
In this, we take all possible inputs and calculate computing time for all of the inputs. Sum all the calculated values and divide the sum by total number of inputs. We must know (or predict) distribution of cases. For the linear search problem, let us assume that all cases are uniformly distributed (including the case of element not being present in the array).

So we sum all the cases and divide the sum by (n+1).


Best Case Analysis (Bogus) 
In this, we calculate lower bound on running time of an algorithm. We must know the case that causes minimum number of operations to be executed. In the linear search problem, the best case occurs when the element is present at the first location.

So time complexity in the best case would be Θ(1)

Analysis of Algorithms - Asymptotic Analysis

Algorithm: An algorithm is step by step instructions to solve a given problem.


Why performance analysis?
There are many important things that should be taken care of, like user friendliness, modularity, security, maintainability, etc. Why to worry about performance?

Evaluation of an algorithm is required to find the most optimized solution for solving a given problem.

For example:
While travelling from Place A to Place B one needs to select the best mode of transport (Flight, Train , Bus etc) based upon the budget and urgency.


Given two algorithms for a task, how to find which one is better?
One way is – implement both the algorithms and run the two programs on your computer for different inputs and see which one takes less time. There are many problems with this approach.
1) It might be possible that for some inputs, first algorithm performs better than the second  and vice versa.
2) Also for some inputs, first algorithm might perform better on one machine and the second works better on other machine for some other inputs.


Asymptotic Analysis is the big idea that handles 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 does the time (or space) taken by an algorithm increase with the input size.

For example: Searching a given item in a sorted array. 
There are 2 ways - Linear and Binary search.

To understand how Asymptotic Analysis solves the above mentioned problems in analyzing algorithms, let us say we run the Linear Search on a fast computer and Binary Search on a slow computer. For small values of input array size, the fast computer may take less time. But, after certain value of input array size, the Binary Search will definitely start taking less time compared to the Linear Search even though the Binary Search is being run on a slow machine.

The reason is the order of growth of Binary Search is logarithmic while that of Linear Search is linear. So the machine dependent constants can always be ignored after certain values of input size.


Does Asymptotic Analysis always work?
Asymptotic Analysis is not perfect, but that’s the best way available for analyzing algorithms.