Data Structure

Analysis of Algorithms | Set 1 (Asymptotic Analysis)

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

The answer to this is simple, we can have all the above things only if we have
performance. So performance is like currency through which we can buy all the above
things. Another reason for studying performance is – speed is fun!

To summarize, performance == scale. Imagine a text editor that can load 1000 pages, but
10 can spell check 1 page per minute OR an image editor that takes 1 hour to rotate your
image 90 degrees left OR … you get it. If a software feature can not cope with the scale
of tasks users need to perform – it is as good as dead.

Given two algorithms for a task, how do we find out which one is better?

One naive way of doing this is – implement both the algorithms and run the two
15 programs on your computer for different inputs and see which one takes less time.
There are many problems with this approach for analysis of algorithms.

1) It might be possible that for some inputs, first algorithm performs better than the
second. And for some inputs second performs better.

2) It might also be possible that for some inputs, first algorithm perform better on one
20 machine and the second works better on other machine for some other inputs.s

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 increases with the input size.

25 For example, let us consider the search problem (searching a given item) in a sorted
array. One way to search is Linear Search (order of growth is linear) and other way is
Binary Search (order of growth is logarithmic). 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
30 of input array size n, 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 with respect to input size logarithmic while the
order of growth of Linear Search is linear. So the machine dependent constants can
always be ignored after certain values of input size.

5 Does Asymptotic Analysis always work?

Asymptotic Analysis is not perfect, but that’s the best way available for analyzing
algorithms. For example, say there are two sorting algorithms that take 1000nLogn and
2nLogn time respectively on a machine. Both of these algorithms are asymptotically
same (order of growth is nLogn). So, With Asymptotic Analysis, we can’t judge which one
10 is better as we ignore constants in Asymptotic Analysis.

Also, in Asymptotic analysis, we always talk about input sizes larger than a constant
value. It might be possible that those large inputs are never given to your software and
an algorithm which is asymptotically slower, always performs better for your particular
situation. So, you may end up choosing an algorithm that is Asymptotically slower but
15 faster for your software.

Analysis of Algorithms | Set 2 (Worst, Average and Best Cases)

We can have three cases to analyze an algorithm:

1) Worst Case

2) Average Case

20 3) Best Case

// Java implementation of the approach 

  
public class GFG {
  
25 // Linearly search x in arr[].  If x is present then return the index,
// otherwise return -1
    static int search(int arr[], int n, int x) {
        int i;
        for (i = 0; i < n; i++) {
30             if (arr[i] == x) {
                return i;
            }
        }
        return -1;
35     }
  
    /* Driver program to test above functions*/
     public static void main(String[] args) {
        int arr[] = {1, 10, 30, 15};
        int x = 30;
        int n = arr.length;
5         System.out.printf("%d is present at index %d", x, search(arr, n, x));
  
    }
}
  
10 Output:
30 is present at index 2
Worst Case Analysis (Usually Done)
In the worst case analysis, we calculate upper bound on running time of an algorithm.
We must know the case that causes maximum number of operations to be executed.
15 For Linear Search, the worst case happens when the element to be searched (x in the
above code) is not present in the array. When x is not present, the search() functions
compares it with all the elements of arr[] one by one. Therefore, the worst case time
complexity of linear search would be Θ(n).
Average Case Analysis (Sometimes done)
20 In average case analysis, 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 x not being
present in array). So we sum all the cases and divide the sum by (n+1). Following is the
25 value of average case time complexity.

Average Case Time =

30 = Θ(n)
Best Case Analysis (Bogus)
In the best case analysis, 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 x is present at the first location. The
35 number of operations in the best case is constant (not dependent on n). So time
complexity in the best case would be Θ(1)
Most of the times, we do worst case analysis to analyze algorithms. In the worst
analysis, we guarantee an upper bound on the running time of an algorithm which is
good information.
 The average case analysis is not easy to do in most of the practical cases and it is rarely
done. In the average case analysis, we must know (or predict) the mathematical
distribution of all possible inputs.
The Best Case analysis is bogus. Guaranteeing a lower bound on an algorithm doesn’t
5 provide any information as in the worst case, an algorithm may take years to run.
For some algorithms, all the cases are asymptotically same, i.e., there are no worst and
best cases. For example, Merge Sort. Merge Sort does Θ(nLogn) operations in all cases.
Most of the other sorting algorithms have worst and best cases. For example, in the
typical implementation of Quick Sort (where pivot is chosen as a corner element), the
10 worst occurs when the input array is already sorted and the best occur when the pivot
elements always divide array in two halves. For insertion sort, the worst case occurs
when the array is reverse sorted and the best case occurs when the array is sorted in
the same order as output.

Analysis of Algorithms | Set 3

15 (Asymptotic Notations)
We have discussed Asymptotic Analysis, and Worst, Average and Best Cases of
Algorithms. The main idea of asymptotic analysis is to have a measure of efficiency of
algorithms that doesn’t depend on machine specific constants, and doesn’t require
20 algorithms to be implemented and time taken by programs to be compared. 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

25 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. For example, consider the following expression.
3n3 + 6n2 + 6000 = Θ(n3)
Dropping lower order terms is always fine because there will always be a n0 after which
30 Θ(n3) has higher values than Θn2) irrespective of the constants involved.
For a given function g(n), we denote Θ(g(n)) is following set of functions.
Θ(g(n)) = {f(n): there exist positive constants c1, c2 and n0 such
 that 0 <= c1*g(n) <= f(n) <= c2*g(n) for all n >= n0}
The above definition means, if f(n) is theta of g(n), then the value f(n) is always between
c1*g(n) and c2*g(n) for large values of n (n >= n0). The definition of theta also requires
that f(n) must be non-negative for values of n greater than n0.
5

2) Big O Notation: The Big O notation defines an upper bound

of an algorithm, it bounds a function only from above. For 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). Note that O(n^2) also
10 covers linear time.
If we use Θ notation to represent time complexity of Insertion sort, we have to use two
statements for best and worst cases:
1. The worst case time complexity of Insertion Sort is Θ(n^2).
2. The best case time complexity of Insertion Sort is Θ(n).
15 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.
O(g(n)) = { f(n): there exist positive constants c and
n0 such that 0 <= f(n) <= c*g(n) for
all n >= n0}

20 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. As discussed in the previous post, the best case performance of an algorithm
is generally not useful, the Omega notation is the least used notation among all three.
For a given function g(n), we denote by Ω(g(n)) the set of functions.
5 Ω (g(n)) = {f(n): there exist positive constants c and
n0 such that 0 <= c*g(n) <= f(n) for
all n >= n0}.
Let us consider the same Insertion sort example here. The time complexity of Insertion
Sort can be written as Ω(n), but it is not a very useful information about insertion sort,
10 as we are generally interested in worst case and sometimes in average case.
Exercise:
Which of the following statements is/are valid?
1. Time Complexity of QuickSort is Θ(n^2)
2. Time Complexity of QuickSort is O(n^2)
15 3. For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) if and only if f(n) = O(g(n))
and f(n) = Ω(g(n)).
4. Time complexity of all computer algorithms can be written as Ω(1)

Analysis of algorithms | little o and

little omega notations
20
The main idea of asymptotic analysis is to have a measure of efficiency of algorithms
that doesn’t depend on machine specific constants, mainly because this analysis doesn’t
require algorithms to be implemented and time taken by programs to be compared. We
have already discussed Three main asymptotic notations. The following 2 more
25 asymptotic notations are used to represent time complexity of algorithms.
Little ο asymptotic notation
Big-Ο is used as a tight upper-bound on the growth of an algorithm’s effort (this effort is
described by the function f(n)), even though, as written, it can also be a loose upper-
bound. “Little-ο” (ο()) notation is used to describe an upper-bound that cannot be tight.
30

Definition : Let f(n) and g(n) be functions that map positive integers to positive real
numbers. We say that f(n) is ο(g(n)) (or f(n) Ε ο(g(n))) if for any real constant c > 0, there
exists an integer constant n0 ≥ 1 such that 0 ≤ f(n) < c*g(n).
 Its means little o() means loose upper-bound of f(n).

In mathematical relation,
5 f(n) = o(g(n)) means
lim  f(n)/g(n) = 0
n→∞

Examples:
10
Is 7n + 8 ∈ o(n2)?
In order for that to be true, for any c, we have to be able to find an n0 that makes
f(n) < c * g(n) asymptotically true.
lets took some example,
15 If c = 100,we check the inequality is clearly true. If c = 1/100 , we’ll have to use
a little more imagination, but we’ll be able to find an n0. (Try n0 = 1000.) From
these examples, the conjecture appears to be correct.
then check limits,
lim  f(n)/g(n) = lim  (7n + 8)/(n2) = lim  7/2n = 0 (l’hospital)
20 n→∞ n→∞ n→∞
hence 7n + 8 ∈ o(n2)
Little ω asymptotic notation
Definition : Let f(n) and g(n) be functions that map positive integers to positive real
numbers. We say that f(n) is ω(g(n)) (or f(n) ∈ ω(g(n))) if for any real constant c > 0,
25 there exists an integer constant n0 ≥ 1 such that f(n) > c * g(n) ≥ 0 for every integer n ≥
n0.
f(n) has a higher growth rate than g(n) so main difference between Big Omega (Ω) and
little omega (ω) lies in their definitions.In the case of Big Omega f(n)=Ω(g(n)) and the
bound is 0<=cg(n)<=f(n), but in case of little omega, it is true for 0<=c*g(n)<f(n).
30
we use ω notation to denote a lower bound that is not asymptotically tight.
and, f(n) ∈ ω(g(n)) if and only if g(n) ∈ ο((f(n)).
 In mathematical relation,
if f(n) ∈ ω(g(n)) then,
lim  f(n)/g(n) = ∞
n→∞
5 Example:
Prove that 4n + 6 ∈ ω(1);
the little omega(ο) running time can be proven by applying limit formula given below.
if lim  f(n)/g(n) = ∞ then functions f(n) is ω(g(n))
n→∞
10 here,we have functions f(n)=4n+6 and g(n)=1
lim   (4n+6)/(1) = ∞
n→∞
and,also for any c we can get n0 for this inequality 0 <= c*g(n) < f(n), 0 <= c*1 < 4n+6
Hence proved.

15 Lower and Upper Bound Theory

The Lower and Upper Bound Theory provides a way to find the lowest complexity
algorithm to solve a problem. Before understanding the theory, first lets have a brief
look on what actually Lower and Upper bounds are.
20  Lower Bound –
Let L(n) be the running time of an algorithm A(say), then g(n) is the Lower
Bound of A if there exist two constants C and N such that L(n) <= C*g(n) for n > N.
Lower bound of an algorithm is shown by the asymptotic notation called Big
Omega (or just Omega).
25  Upper Bound –
Let U(n) be the running time of an algorithm A(say), then g(n) is the Upper
Bound of A if there exist two constants C and N such that U(n) >= C*g(n) for n > N.
Upper bound of an algorithm is shown by the asymptotic notation called Big
Oh(O) (or just Oh).
30 1. Lower Bound Theory:
According to the lower bound theory, for a lower bound L(n) of an algorithm, it is not
possible to have any other algorithm (for a common problem) whose time complexity is
less than L(n) for random input. Also every algorithm must take at least L(n) time in
worst case. Note that L(n) here is the minimum of all the possible algorithm, of
35 maximum complexity.

The Lower Bound is a very important for any algorithm. Once we calculated it, then we
can compare it with the actual complexity of the algorithm and if their order are same
 then we can declare our algorithm as optimal. So in this section we will be discussing
about techniques for finding the lower bound of an algorithm.
Note that our main motive is to get an optimal algorithm, which is the one having its
Upper Bound Same as its Lower Bound (U(n)=L(n)). Merge Sort is a common example of
5 an optimal algorithm.
Trivial Lower Bound –
It is the easiest method to find the lower bound. The Lower bounds which can be easily
observed on the basis of the number of input taken and the number of output produces
are called Trivial Lower Bound.
10 Example: Multiplication of n x n matrix, where,
Input: For 2 matrix we will have 2n2 inputsOutput: 1 matrix of order n x n, i.e., n 2 outputs
In the above example its easily predictable that the lower bound is O(n 2).
Computational Model –
The method is for all those algorithms that are comparison based. For example in
15 sorting we have to compare the elements of the list among themselves and then sort
them accordingly. Similar is the case with searching and thus we can implement the
same in this case. Now we will look at some examples to understand its usage.
Ordered Searching –
It is a type of searching in which the list is already sorted.
20 Example-1: Linear search
Explanation –
In linear search we compare the key with first element if it does not match we compare
with second element and so on till we check against the nth element. Else we will end
up with a failure.
25 Example-2: Binary search
Explanation –
In binary search, we check the middle element against the key, if it is greater we search
the first half else we check the second half and repeat the same process.
The diagram below there is an illustration of binary search in an array consisting of 4
30 elements
 Calculating the lower bound: The max no of comparisons are n. Let there be k levels in
the tree.
5 1. No. of nodes will be 2k-1
2. The upper bound of no of nodes in any comparison based search of an element
in list of size n will be n as there are maximum of n comparisons in worst case
scenario 2k-1
3. Each level will take 1 comparison thus no. of comparisons k≥|log2n|
10 Thus the lower bound of any comparison based search from a list of n elements cannot
be less than log(n). Therefore we can say that Binary Search is optimal as its complexity
is Θ(log n).
Sorting –
The diagram below is an example of tree formed in sorting combinations with 3
15 elements.
 Example – For n elements, finding lower bound using computation model.
Explanation –
For n elements we have a total on n! combinations (leaf nodes). (Refer the diagram the
5 total combinations are 3! or 6) also it is clear that the tree formed is a binary tree. Each
level in the diagram indicates a comparison. Let there be k levels => 2 k is the total
number of leaf nodes in a full binary tree thus in this case we have n!≤2 k.
As the k in the above example is the no of comparisons thus by computational model
lower bond = k.
10 Now we can say that,n!≤2T(n)
Thus,
T(n)>|log n!|
=> n!<=nn
Thus,
15 log n!<=log nn
Taking ceiling function on both sides, we get
|-log nn-|>=|-log n!-|
Thus complexity becomes Θ(lognn) or Θ(nlogn)
Using Lower bond theory to solve algebraic problem:
20 1. Straight Line Program –
The type of programs build without any loops or control structures is called
Straight Line Program. For example,
 //summing to nos
Sum(a, b)
{
    //no loops and no control structures
    c:= a+b;
    return c;
}
2.
3. Algebraic Problem –
Problems related to algebra like solving equations inequalities etc., comes under
5 algebraic problems. For example, solving equation ax2+bx+c with simple
programming.

Algo_Sol(a, b, c, x)
{ 
    //1 assignment
    v:=a*x; 
  
    //1 assignment
    v:=v+b;
  
    //1 assignment
    v:=v*x;
  
    //1 assignment
    ans:=v+c;
    return ans;
}    
4.
Complexity for solving here is 4 (excluding the returning).
10 5.
The above example shows us a simple way to solve an equation for 2 degree polynomial
i.e., 4 thus for nth degree polynomial we will have complexity of O(n 2).
6.
Let us demonstrate via an algorithm.
15 7.
Example: anxn+an-1xn-1+an-2xn-2+…+a1x+a0 is a polynomial of degree n.

pow(x, n) 
  { 
    p := 1; 
    
    //loop from 1 to n 
    for i:=1 to n 
         p := p*x; 
  
    return p; 
  } 
  
polynomial(A, x, n) 
  { 
     int p, v:=0; 
     for i := 0 to n 
    
         //loop within a loop from 0 to n
         v := v + A[i]*pow(x, i); 
     return v; 
  } 
8.
Loop within a loop => complexity = O(n2);
9.
Now to find an optimal algorithm we need to find the lower bound here (as per lower
5 bound theory). As per Lower Bound Theory, The optimal algorithm to solve the above
problem is the one having complexity O(n). Lets prove this theorem using lower bounds.
10.
Theorem: To prove that optimal algo of solving a n degree polynomial is O(n)
Proof: The best solution for reducing the algo is to make this problem less complex by
10 dividing the polynomial into several straight line problems.
11.
=> anxn+an-1xn-1+an-2xn-2+...+a1x+a0
can be written as,
((..(anx+an-1)x+..+a2)x+a1)x+a0
15 Now, algorithm will be as,
v=0
v=v+an
v=v*x
v=v+an-1
20 v=v*x
...
v=v+a1
v=v*x
v=v+a0
25
 polynomial(A, x, n) 
     {
      int p, v=0; 
  
      // loop executed n times
      for i = n to 0 
             v = (v + A[i])*x;
  
         return v;
      }
12.
Clearly, the complexity of this code is O(n). This way of solving such equations is called
Horner’s method. Here is were lower bound theory works and give the optimum
algorithm’s complexity as O(n).
5 13.
2. Upper Bound Theory:
According to the upper bound theory, for an upper bound U(n) of an algorithm, we can
always solve the problem in at most U(n) time.Time taken by a known algorithm to solve
a problem with worse case input gives us the upper bound.

10 Analysis of Algorithms | Set 4 (Analysis

of Loops)
1) O(1): Time complexity of a function (or set of statements) is considered as O(1) if it
doesn’t contain loop, recursion and call to any other non-constant time function.
15 // set of non-recursive and non-loop statements
For example swap() function has O(1) time complexity.
A loop or recursion that runs a constant number of times is also considered as O(1). For
example the following loop is O(1).

20 // Here c is a constant
for (int i = 1; i <= c; i++) {
// some O(1) expressions
}
2) O(n): Time Complexity of a loop is considered as O(n) if the loop variables is
25 incremented / decremented by a constant amount. For example following functions
have O(n) time complexity.
// Here c is a positive integer constant
 for (int i = 1; i <= n; i += c) {
// some O(1) expressions
}

5 for (int i = n; i > 0; i -= c) {

// some O(1) expressions
}
3) O(nc): Time complexity of nested loops is equal to the number of times the innermost
statement is executed. For example the following sample loops have O(n 2) time
10 complexity

for (int i = 1; i <=n; i += c) {

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

for (int i = n; i > 0; i -= c) {

for (int j = i+1; j <=n; j += c) {
20 // some O(1) expressions
}
For example Selection sort and Insertion Sort have O(n2) time complexity.
4) O(Logn) Time Complexity of a loop is considered as O(Logn) if the loop variables is
divided / multiplied by a constant amount.
25 for (int i = 1; i <=n; i *= c) {
// some O(1) expressions
}
for (int i = n; i > 0; i /= c) {
// some O(1) expressions
30 }
For example Binary Search(refer iterative implementation) has O(Logn) time complexity.
Let us see mathematically how it is O(Log n). The series that we get in first loop is 1, c,
 c2, c3, … ck. If we put k equals to Logcn, we get cLogcn which is n.
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.
// Here c is a constant greater than 1
5 for (int i = 2; i <=n; i = pow(i, c)) {
// some O(1) expressions
}
//Here fun is sqrt or cuberoot or any other constant root
for (int i = n; i > 1; i = fun(i)) {
10 // some O(1) expressions
}
See this for mathematical details.
How to combine time complexities of consecutive loops?
When there are consecutive loops, we calculate time complexity as sum of time
15 complexities of individual loops.
for (int i = 1; i <=m; i += c) {
// some O(1) expressions
}
for (int i = 1; i <=n; i += c) {
20 // some O(1) 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
25 loops?
As discussed here, 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
30 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.

Analysis of Algorithm | Set 4 (Solving

Recurrences)
 In the previous post, we discussed analysis of loops. Many algorithms are recursive in
nature. When we analyze them, we get a recurrence relation for time complexity. We
get running time on an input of size n as a function of n and the running time on inputs
5 of smaller sizes. For example in Merge Sort, to sort a given array, we divide it in two
halves and recursively repeat the process for the two halves. Finally we merge the
results. Time complexity of Merge Sort can be written as T(n) = 2T(n/2) + cn. There are
many other algorithms like Binary Search, Tower of Hanoi, etc.
There are mainly three ways for solving recurrences.
10 1) Substitution Method: We make a guess for the solution and then we use
mathematical induction to prove the guess is correct or incorrect.

For example consider the recurrence T(n) = 2T(n/2) + n

15 We guess the solution as T(n) = O(nLogn). Now we use induction

to prove our guess.

We need to prove that T(n) <= cnLogn. We can assume that it is true
for values smaller than n.
20

T(n) = 2T(n/2) + n
<= cn/2Log(n/2) + n
= cnLogn - cnLog2 + n
= cnLogn - cn + n
25 <= cnLogn
2) Recurrence Tree Method: In this method, we draw a recurrence tree and calculate
the time taken by every level of tree. Finally, we sum the work done at all levels. To
draw the recurrence tree, we start from the given recurrence and keep drawing till we
find a pattern among levels. The pattern is typically a arithmetic or geometric series.
30 For example consider the recurrence relation
T(n) = T(n/4) + T(n/2) + cn2

cn2
 / \
T(n/4) T(n/2)

If we further break down the expression T(n/4) and T(n/2),

5 we get following recursion tree.

cn2
/ \
c(n2)/16 c(n2)/4
10 / \ / \
T(n/16) T(n/8) T(n/8) T(n/4)
Breaking down further gives us following
cn2
/ \
15 c(n2)/16 c(n2)/4
/ \ / \
c(n2)/256 c(n2)/64 c(n2)/64 c(n2)/16
/ \ / \ / \ / \

20 To know the value of T(n), we need to calculate sum of tree

nodes level by level. If we sum the above tree level by level,
we get the following series
T(n) = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + ....
The above series is geometrical progression with ratio 5/16.
25

To get an upper bound, we can sum the infinite series.

We get the sum as (n2)/(1 - 5/16) which is O(n2)
3) Master Method:
Master Method is a direct way to get the solution. The master method works only for
 following type of recurrences or for recurrences that can be transformed to following
type.
T(n) = aT(n/b) + f(n) where a >= 1 and b > 1
There are following three cases:
5 1. If f(n) = Θ(nc) where c < Logba then T(n) = Θ(nLogba)
2. If f(n) = Θ(nc) where c = Logba then T(n) = Θ(ncLog n)
3.If f(n) = Θ(nc) where c > Logba then T(n) = Θ(f(n))
How does this work?
Master method is mainly derived from recurrence tree method. If we draw recurrence
10 tree of T(n) = aT(n/b) + f(n), we can see that the work done at root is f(n) and work done
at all leaves is Θ(nc) where c is Logba. And the height of recurrence tree is Logbn

In recurrence tree method, we calculate total work done. If the work done at leaves is
polynomially more, then leaves are the dominant part, and our result becomes the work
15 done at leaves (Case 1). If work done at leaves and root is asymptotically same, then our
result becomes height multiplied by work done at any level (Case 2). If work done at
root is asymptotically more, then our result becomes work done at root (Case 3).
Examples of some standard algorithms whose time complexity can be evaluated using
Master Method
20 Merge Sort: T(n) = 2T(n/2) + Θ(n). It falls in case 2 as c is 1 and Logba] is also 1. So the
solution is Θ(n Logn)
Binary Search: T(n) = T(n/2) + Θ(1). It also falls in case 2 as c is 0 and Logba is also 0. So
the solution is Θ(Logn)
Notes:
25 1) It is not necessary that a recurrence of the form T(n) = aT(n/b) + f(n) can be solved
using Master Theorem. The given three cases have some gaps between them. For
example, the recurrence T(n) = 2T(n/2) + n/Logn cannot be solved using master method.
 2) Case 2 can be extended for f(n) = Θ(ncLogkn)
If f(n) = Θ(ncLogkn) for some constant k >= 0 and c = Logba, then T(n) = Θ(ncLogk+1n)

What does ‘Space Complexity’ mean?

5 Space Complexity:
The term Space Complexity is misused for Auxiliary Space at many places. Following are
the correct definitions of Auxiliary Space and Space Complexity.
Auxiliary Space is the extra space or temporary space used by an algorithm.
Space Complexity of an algorithm is total space taken by the algorithm with respect to
10 the input size. Space complexity includes both Auxiliary space and space used by input.

For example, if we want to compare standard sorting algorithms on the basis of space,
then Auxiliary Space would be a better criteria than Space Complexity. Merge Sort uses
O(n) auxiliary space, Insertion sort and Heap Sort use O(1) auxiliary space. Space
15 complexity of all these sorting algorithms is O(n) though.

Analysis of Algorithms | Set 5 (Practice

Problems)
We have discussed Asymptotic Analysis, Worst, Average and Best Cases , Asymptotic
20 Notations and Analysis of loops in previous posts.
In this post, practice problems on analysis of algorithms are discussed.
Problem 1: Find the complexity of below recurrence:

{ 3T(n-1), if n>0,
25 T(n) = { 1, otherwise
Solution:
Let us solve using substitution.
T(n) = 3T(n-1)
= 3(3T(n-2))
30 = 32T(n-2)
= 33T(n-3)
 ...
...
= 3nT(n-n)
= 3nT(0)
5 = 3n
This clearly shows that the complexity
of this function is O(3n).
 
Problem 2: Find the complexity of the recurrence:
10 { 2T(n-1) - 1, if n>0,
T(n) = { 1, otherwise
Solution:
Let us try solving this function with substitution.
T(n) = 2T(n-1) - 1
15 = 2(2T(n-2)-1)-1
= 22(T(n-2)) - 2 - 1
= 22(2T(n-3)-1) - 2 - 1
= 23T(n-3) - 22 - 21 - 20
.....
20 .....
= 2nT(n-n) - 2n-1 - 2n-2 - 2n-3
..... 22 - 21 - 20

= 2n - 2n-1 - 2n-2 - 2n-3

25 ..... 22 - 21 - 20
= 2n - (2n-1)
[Note: 2n-1 + 2n-2 + ...... + 20 = 2n ]
T(n) = 1
Time Complexity is O(1). Note that while
 the recurrence relation looks exponential
the solution to the recurrence relation
here gives a different result.
 
5 Problem 3: Find the complexity of the below program:
function(int n)
{
    if (n==1)
       return;
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
            printf("*");
            break;
        }
    }
}
Solution: Consider the comments in the following function.
function(int n)
{
    if (n==1)
       return;
    for (int i=1; i<=n; i++)
    {
        // Inner loop executes only one
        // time due to break statement.
        for (int j=1; j<=n; j++)
        {
            printf("*");
            break;
        }
    }
}
Time Complexity of the above function O(n). Even though the inner loop is bounded by
n, but due to break statement it is executing only once.
 
10 Problem 4: Find the complexity of the below program:
void function(int n)
 {
    int count = 0;
    for (int i=n/2; i<=n; i++)
        for (int j=1; j<=n; j = 2 * j)
            for (int k=1; k<=n; k = k * 2)
                count++;
}
Solution: Consider the comments in the following function.
void function(int n)
{
    int count = 0;
    for (int i=n/2; i<=n; i++)
  
        // Executes O(Log n) times
        for (int j=1; j<=n; j = 2 * j)
  
            // Executes O(Log n) times
            for (int k=1; k<=n; k = k * 2)
                count++;
}
Time Complexity of the above function O(n log2n).
 
Problem 5: Find the complexity of the below program:
void function(int n)
{
    int count = 0;
    for (int i=n/2; i<=n; i++)
        for (int j=1; j+n/2<=n; j = j++)
            for (int k=1; k<=n; k = k * 2)
                count++;
}
5 Solution: Consider the comments in the following function.
void function(int n)
{
    int count = 0;
  
    // outer loop executes n/2 times
    for (int i=n/2; i<=n; i++)
  
        // middle loop executes  n/2 times
        for (int j=1; j+n/2<=n; j = j++)
   
            // inner loop executes logn times
            for (int k=1; k<=n; k = k * 2)
                count++;
}
Time Complexity of the above function O(n2logn).
 
Problem 6: Find the complexity of the below program:
void function(int n)
{
    int i = 1, s =1;
    while (s <= n)
    {
        i++;
        s += i;
        printf("*");
    }
}
Solution: We can define the terms ‘s’ according to relation si = si-1 + i. The value of ‘i’
5 increases by one for each iteration. The value contained in ‘s’ at the ith iteration is the
sum of the first ‘i’ positive integers. If k is total number of iterations taken by the
program, then while loop terminates if: 1 + 2 + 3 ….+ k = [k(k+1)/2] > n So k = O(√n).
Time Complexity of the above function O(√n).

10  
Problem 7: Find a tight upper bound on complexity of the below program:
void function(int n)
{
    int count = 0;
    for (int i=0; i<n; i++)
        for (int j=i; j< i*i; j++)
            if (j%i == 0)
            {
                for (int k=0; k<j; k++)
                    printf("*");
            }
}
Solution:Consider the comments in the following function.
void function(int n)
{
     int count = 0;
  
    // executes n times
    for (int i=0; i<n; i++)
  
        // executes O(n*n) times.
        for (int j=i; j< i*i; j++)
            if (j%i == 0)
            {
                // executes j times = O(n*n) times
                for (int k=0; k<j; k++)
                    printf("*");
            }
}
Time Complexity of the above function O(n5).
1. What is the time, space complexity of following code:
int a = 0, b = 0;
for (i = 0; i < N; i++) {
    a = a + rand();
}
for (j = 0; j < M; j++) {
    b = b + rand();
}
Options:

5 1. O(N * M) time, O(1) space

2. O(N + M) time, O(N + M) space
3. O(N + M) time, O(1) space
4. O(N * M) time, O(N + M) space
Output:
10 3. O(N + M) time, O(1) space
Explanation: The first loop is O(N) and the second loop is O(M). Since we don’t know
which is bigger, we say this is O(N + M). This can also be written as O(max(N, M)).
Since there is no additional space being utilized, the space complexity is constant / O(1)
2. What is the time complexity of following code:
int a = 0;
for (i = 0; i < N; i++) {
    for (j = N; j > i; j--) {
        a = a + i + j;
     }
}
Options:
1. O(N)
2. O(N*log(N))
3. O(N * Sqrt(N))
5 4. O(N*N)
Output:
4. O(N*N)
Explanation:
The above code runs total no of times
10 = N + (N – 1) + (N – 2) + … 1 + 0
= N * (N + 1) / 2
= 1/2 * N^2 + 1/2 * N
O(N^2) times.
3. What is the time complexity of following code:
int i, j, k = 0;
for (i = n / 2; i <= n; i++) {
    for (j = 2; j <= n; j = j * 2) {
        k = k + n / 2;
    }
}
15 Options:
1. O(n)
2. O(nLogn)
3. O(n^2)
4. O(n^2Logn)
20 Output:
2. O(nLogn)
Explanation:If you notice, j keeps doubling till it is less than or equal to n. Number of
times, we can double a number till it is less than n would be log(n).
Let’s take the examples here.
25 for n = 16, j = 2, 4, 8, 16
for n = 32, j = 2, 4, 8, 16, 32
So, j would run for O(log n) steps.
i runs for n/2 steps.
So, total steps = O(n/ 2 * log (n)) = O(n*logn)
30
 4. What does it mean when we say that an algorithm X is asymptotically more efficient
than Y?
Options:
1. X will always be a better choice for small inputs
5 2. X will always be a better choice for large inputs
3. Y will always be a better choice for small inputs
4. X will always be a better choice for all inputs
2. X will always be a better choice for large inputs
Explanation: In asymptotic analysis we consider growth of algorithm in terms of input
10 size. An algorithm X is said to be asymptotically better than Y if X takes smaller time than
y for all input sizes n larger than a value n0 where n0 > 0.

5. What is the time complexity of following code:

int a = 0, i = N;
while (i > 0) {
    a += i;
    i /= 2;
}
Options:
1. O(N)
15 2. O(Sqrt(N))
3. O(N / 2)
4. O(log N)
Output:
4. O(log N)
20 Explanation: We have to find the smallest x such that N / 2^x N
x = log(N)

Practice Set for Recurrence Relations

Que-1. Solve the following recurrence relation?
T(n) = 7T(n/2) + 3n^2 + 2
25 (a) O(n^2.8)
(b) O(n^3)
(c) θ(n^2.8)
(d) θ(n^3)
Explanation –
30 T(n) = 7T(n/2) + 3n^2 + 2
As one can see from the formula above:
 a = 7, b = 2, and f(n) = 3n^2 + 2
So, f(n) = O(n^c), where c = 2.
It falls in master’s theorem case 1:
logb(a) = log2(7) = 2.81 > 2
5 It follows from the first case of the master theorem that T(n) = θ(n^2.8) and implies
O(n^2.8) as well as O(n^3).
Therefore, option (a), (b), and (c) are correct options.

Que-2. Sort the following functions in the decreasing order of their asymptotic (big-O)
10 complexity:
f1(n) = n^√n , f2(n) = 2^n, f3(n) = (1.000001)^n , f4(n) = n^(10)*2^(n/2)
(a) f2> f4> f1> f3
(b) f2> f4> f3> f1
(c) f1> f2> f3> f4
15 (d) f2> f1> f4> f3
Explanation –
f2 > f4 because we can write f2(n) = 2^(n/2)*2^(n/2), f4(n) = n^(10)*2^(n/2) which
clearly shows that f2 > f4
f4 > f3 because we can write f4(n) = n^10.〖√2〗^n = n10.(1.414)n , which clearly
20 shows f4> f3
f3> f1:
f1 (n) = n^√n take log both side log f1 = √n log n
f3 (n) = (1.000001)^n take log both side log f3 = n log(1.000001), we can write as log f3 =
√n*√n log(1.000001) and √n > log(1.000001).
25 So, correct order is f2> f4> f3> f1. Option (b) is correct.
Que-3. f(n) = 2^(2n)
Which of the following correctly represents the above function?
(a) O(2^n)
(b) Ω(2^n)
30 (c) Θ(2^n)
(d) None of these
Explanation – f(n) = 2^(2n) = 2^n*2^n
Option (a) says f(n)<= c*2n, which is not true. Option (c) says c1*2n <= f(n) <= c2*2n,
lower bound is satisfied but upper bound is not satisfied. Option (b) says c*2n <= f(n)
35 this condition is satisfied hence option (b) is correct.
Que-4. Master’s theorem can be applied on which of the following recurrence relation?
(a) T (n) = 2T (n/2) + 2^n
(b) T (n) = 2T (n/3) + sin(n)
(c) T (n) = T (n-2) + 2n^2 + 1
40 (d) None of these
 Explanation – Master theorem can be applied to the recurrence relation of the
following type
T (n) = aT(n/b) + f (n)
Option (a) is wrong because to apply master’s theorem, function f(n) should be
5 polynomial.
Option (b) is wrong because in order to apply master theorem f(n) should be
monotonically increasing function.
Option (c) is not the above mentioned type, therefore correct answer is (d).
Que-5. T(n) = 3T(n/2+ 47) + 2n^2 + 10*n – 1/2. T(n) will be
10 (a) O(n^2)
(b) O(n^(3/2))
(c) O(n log n)
(d) None of these
Explanation – For higher values of n, n/2 >> 47, so we can ignore 47, now T(n) will be
15 T(n) = 3T(n/2)+ 2*n^2 + 10*n – 1/2 = 3T(n/2)+ O(n^2)
Apply master theorem, it is case 2 of master theorem T(n) = O(n^2).
Option (a) is correct.