Mekelle University

School of Computing, EiT-M, MU - Computer Science Department

Data Structures and Algorithms - Chapter 2 – Algorithm Design and Analysis

Introduction

This chapter mainly focuses on two important aspects of algorithms: Algorithm design and Algorithm
Analysis. The first section emphasizes on some of the algorithm design techniques that have proved
their utility in the solution to many problems.

Whereas the second section of this chapter deals with Algorithm Analysis. So far we have not
considered in any rigorous and careful way how efficient our algorithms are in terms of how much
work they need to do and how much memory they consume. In this chapter we will lay out an
approach for analyzing algorithms and demonstrate how to use it on several simple algorithms. We
will mainly be concerned with analyzing the amount of work done by algorithms; occasionally we will
consider how much memory they consume as well.

2.1. Algorithm design

Algorithm Design Strategies/Techniques/Paradigm

What is an algorithm design technique?

An algorithm design technique (or “strategy” or “paradigm”) is a general approach to solving

problems algorithmically that is applicable to a variety of problems from different areas of computing.

This portion deals with individual known design techniques. They distill a few key ideas that have
proven to be useful in designing algorithms. Learning these techniques is of utmost importance for the
following reasons.

First, they provide guidance for designing algorithms for new problems, i.e., problems for which there
is no known satisfactory algorithm. Therefore—to use the language of a famous proverb—learning
such techniques is akin to learning to fish as opposed to being given a fish caught by somebody else. It
is not true, of course, that each of these general techniques will be necessarily applicable to every
problem you may encounter. But taken together, they do constitute a powerful collection of tools that
you will find quite handy in your studies and work.

Second, algorithms are the cornerstone of computer science. Every science is interested in classifying
its principal subject, and computer science is no exception. Algorithm design techniques make it
possible to classify algorithms according to an underlying design idea; therefore, they can serve as a
natural way to both categorize and study algorithms.

Third, one of the most importance aspects of algorithm design is creating an algorithm that has an
efficient runtime.

Algorithms are often designed using common techniques, including:

a) Brute-force algorithm

Brute-force is a very general problem-solving technique that consists of systematically enumerating all
possible candidates for the solution and checking whether each candidate satisfies the problem’s
statement. And often, the brute-force strategy is indeed the one that is easiest to apply.

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 1|Page

Brute force is a straightforward approach to solving a problem, usually directly based on the problem
statement and definitions of the concepts involved.

Approach
- Based on trying all possible solutions (Exhaustive search: Explores all possible solutions without
any clever shortcuts.)
- Generate and evaluate possible solutions until
 Satisfactory solution is found
 Best solution is found (if can be determined)
 All possible solutions found
- Return best solution
- Return failure if no satisfactory solution
- Generally most expensive approach
- Simple to implement: Often involves simple loops or recursion.
- Guarantees finding a solution: If a solution exists, it will eventually be found.
- Can be slow or impractical for large problems: Runtime increases exponentially with problem
size.

Example: Common problems solved using brute-force algorithms:

1. Finding a Password: Trying all possible combinations of characters until the correct password is
found.
2. Solving Word Puzzles: Generating and checking all possible word combinations to solve
crosswords, cryptograms, or anagrams.
3. Finding a Path in a Maze: Trying all possible paths to find a way out of a maze.
4. Playing Games: Evaluating all possible moves in games like tic-tac-toe or checkers to choose the
best one.
5. Traveling Salesman Problem (TSP): Trying all possible routes to find the shortest path that
visits all cities and returns to the starting point.
6. Subset Sum Problem: Determining whether a subset of numbers in a set adds up to a given target
value.
7. Knapsack Problem: Choosing items to fill a knapsack with a maximum weight
capacity, maximizing the total value of the items.
8. Graph Coloring: Assigning colors to vertices of a graph so that no two adjacent vertices have the
same color.

Advantages of brute-force algorithms:

 Simple to understand and implement.

 Guarantee to find a solution if one exists.
 Versatile, applicable to a wide range of problems.

Disadvantages:

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 2|Page

  Can be very inefficient for large problem spaces.
 Not practical for problems where the solution space is too large to explore exhaustively.
 May not find the optimal solution, only a feasible one.

b) Recursive algorithm

The process of solving a problem by reducing it to smaller versions of itself is called recursion. A
recursive algorithm is an algorithm that calls itself. When a recursive algorithm calls itself, it
performs the same over again. This repetition of steps is somewhat similar to the effect we get when
the steps are part of a loop. Indeed, often the same algorithm can be expressed either iteratively (using
loop) or recursively.

Example: In an algebra course, you probably learned how to find the factorial of a nonnegative
integer. For example, the factorial of 5, written 5!, is 5 x 4 x 3 x 2 x 1 = 120. Similarly, 4! = 4 x 3 x 2 x
1 = 24. Also, factorial of 0 is defined to be 0! = 1. Note that 5! = 5 x 4 x 3 x 2 x 1 = 5 x ( 4 x 3 x 2 x 1 )
= 5x 4!. In general, if n is a nonnegative, the factorial of n, written as n! can be defined as follows:

0! = 1 (Equation 1-1)
n! = n x (n – 1)! if n > 0 (Equation 1-2)

In this definition, 0! is defined to be 1, and if n is an integer greater than 0, first we find (n - 1)! and
then multiply it by n. To find (n - 1)!, we apply the definition again. If (n - 1) > 0, then we use
Equation 1-2; otherwise, we use Equation 1-1. Thus, for an integer n greater than 0, n! is obtained by
first finding (n - 1)! and then multiplying (n - 1)! by n.

Let us apply this definition to find 3!. Here n = 3. Because n > 0, we use Equation 1-2 to obtain:

3! = 3 x 2!

Next, we find 2! Here n = 2. Because n > 0, we use Equation 1-2 to obtain:

2! = 2 x 1!

Now to find 1!, we again use Equation 1-2 because n = 1 > 0. Thus:

1! = 1 x 0!

Finally, we use Equation 1-1 to find 0!, which is 1. Substituting 0! into 1! gives 1! = 1. This gives 2! =
2 x 1! = 2 x 1 = 2, which in turn gives 3! = 3 x 2! = 3 x 2 = 6.

The solution in Equation 1-1 is direct—that is, the right side of the equation contains no factorial
notation. The solution in Equation 1-2 is given in terms of a smaller version of itself. The definition of
the factorial given in Equations 1-1 and 1-2 is called a recursive definition. Equation 1-1 is called the
base case (that is, the case for which the solution is obtained directly); Equation 1-2 is called the
general case.

Recursive definition: A definition in which something is defined in terms of a smaller version of

itself. From the previous example (factorial), it is clear that:

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 3|Page

 1. Every recursive definition must have one (or more) base cases.
2. The general case must eventually be reduced to a base case.
3. The base case stops the recursion.

The concept of recursion in computer science works similarly. Here, we talk about recursive
algorithms and recursive functions. An algorithm that finds the solution to a given problem by
reducing the problem to smaller versions of itself is called a recursive algorithm. The recursive
algorithm must have one or more base cases, and the general solution must eventually be reduced to a
base case.

A function that calls itself is called a recursive function. That is, the body of the recursive function
contains a statement that causes the same function to execute again before completing the current call.
Recursive algorithms are implemented using recursive functions.

Next, let us write the recursive function that implements the factorial function.

int fact(int num)

{
if (num == 0)
return 1;
else
return num * fact(num - 1);
}

Figure below traces the execution of the following statement: cout << fact(3) << endl;

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 4|Page

The output of the previous cout statement is: 6

In the above Figure, the down arrow represents the successive calls to the function fact, and the
upward arrows represent the values returned to the caller, that is, the calling function.

Let us note the following from the previous example, involving the factorial function:

 Logically, you can think of a recursive function as having an unlimited number of copies of
itself.
 Every call to a recursive function—that is, every recursive call—has its own code and its own set
of parameters and local variables.
 After completing a particular recursive call, control goes back to the calling environment, which
is the previous call. The current (recursive) call must execute completely before control goes
back to the previous call. The execution in the previous call begins from the point immediately
following the recursive call.

Other Examples: Common problems solved using recursive algorithms:

1. Factorial Calculation:
 Factorial of a non-negative integer n (n!) is the product of all positive integers less than or
equal to n.
 factorial(n) = n * factorial(n-1) (base case: factorial(0) = 1)

2. Fibonacci Sequence:
 Sequence where each number is the sum of the two preceding ones, starting from 0 and 1.
 Recursive definition: F(n) = F(n-1) + F(n-2), with base cases F(0) = 0 and F(1) = 1.
fib(n) = fib(n-1) + fib(n-2) (base cases: fib(0) = 0, fib(1) = 1)

3. Tree Traversals (preorder, inorder, postorder):

Visit a node, then recursively visit its children in a specific order.

4. Tower of Hanoi:
Move disks between towers recursively, following specific rules.

5. Merge Sort:
Divide a list into halves, sort them recursively, and merge the sorted halves.

6. Quick Sort:
Choose a pivot, partition the list around it, and recursively sort the sublists.

7. Depth-First Search (DFS):

Explore a graph or tree by recursively visiting nodes in a depth-first manner.

8. Permutations and Combinations:

Generate all possible arrangements or selections of elements recursively.

Advantages of recursive algorithms:

 Elegant and concise code: Often lead to clear and readable solutions.

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 5|Page

 Natural for problems with self-similar structure: Well-suited for problems that can be divided
into smaller, similar subproblems.
 Can simplify complex problems: Break down problems into more manageable steps.

Disadvantages of recursive algorithms:

 Can be less efficient: Due to function call overhead and potential for redundant calculations.
 Risk of stack overflow: Recursive calls can consume a lot of memory, leading to stack overflow
errors for large problems.
 Can be harder to debug: Tracing execution flow through recursion can be challenging.

c) Greedy Algorithm

Greedy algorithm design is a technique that involves making the locally optimal choice at each
step, hoping to reach a global optimum solution. It's often efficient and straightforward, but it
doesn't always guarantee the best solution.

Key features:

 Locally optimal choices: The algorithm prioritizes the best immediate option without
considering future consequences.
 Step-by-step construction: The solution is built incrementally, one choice at a time.
 No backtracking: Once a choice is made, it's not revisited or undone.
 Not always optimal: Greedy algorithms can lead to suboptimal solutions in some cases.

Example:
Here's a clear example of the coin change problem using the greedy algorithm, demonstrating its
potential pitfalls:

Problem: Make change for 63 cents using coins of denominations 1, 5, 10, and 25 cents.

Greedy Algorithm Steps:

1. Start with the largest denomination: Use as many 25-cent coins as possible: 63 ÷ 25 = 2 with a
remainder of 13.
2. Move to the next largest denomination: Use as many 10-cent coins as possible: 13 ÷ 10 = 1 with
a remainder of 3.
3. Continue with the next largest denomination: Use as many 5-cent coins as possible: 3 ÷ 5 = 0
with a remainder of 3.
4. Finish with the smallest denomination: Use the remaining 3 cents in 1-cent coins.

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 6|Page

 Greedy Algorithm's Solution: 2 quarters (25 cents), 1 dime (10 cents), and 3 pennies (1 cent).

Total Coins: 6

Common problems solved using greedy algorithms:

1. Coin Change Problem: Finding the minimum number of coins to make a given amount of
change.
2. Dijkstra's Shortest Path Algorithm: Finding the shortest path between nodes in a weighted
graph.
3. Prim's Minimum Spanning Tree Algorithm: Finding a minimum spanning tree in a graph.
4. Kruskal's Minimum Spanning Tree Algorithm: Another algorithm for finding a minimum
spanning tree.
5. Huffman Coding: Building a compression code for data transmission.
6. Activity Selection Problem: Selecting the maximum number of non-overlapping activities that
can be completed within a given time frame.
7. Job Scheduling: Scheduling jobs to minimize completion time or maximize profit.
8. Knapsack Problem (greedy approximation): Filling a knapsack with items to maximize value
while staying within a weight limit.

Advantages of greedy algorithms:

 Simple to understand and implement: Often have intuitive logic and straightforward code.
 Efficient: Usually have low time and space complexity.
 Work well for many problems: Effective for a variety of optimization problems.

Disadvantages of greedy algorithms:

 Not always optimal: Can miss the global optimum solution in some cases.
 Difficult to prove optimality: Proving that a greedy algorithm always produces the optimal
solution can be challenging.
 Sensitive to problem structure: Their success depends heavily on the specific problem structure
and whether the greedy choice leads to the overall optimal solution.
d) Divide-and-conquer

Divide-and-conquer is probably the best-known general algorithm design technique. Though its
fame may have something to do with its catchy name, it is well deserved: quite a few very efficient
algorithms are specific implementations of this general strategy. Divide-and-conquer algorithms
work according to the following general plan:

1. A problem is divided into several sub-problems of the same type, ideally of about equal size.

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 7|Page

 2. The sub-problems are solved (typically recursively, though sometimes a different algorithm is
employed, especially when sub-problems become small enough).
3. If necessary, the solutions to the sub-problems are combined to get a solution to the original
problem.

The divide-and-conquer technique is diagrammed in Figure 1.3, which depicts the case of dividing
a problem into two smaller sub-problems, by far the most widely occurring case.

Figure: 1.3: Divide-and-conquer technique (typical case).

As an example, let us consider the problem of computing the sum of n numbers a0, . . . , an− 1. If n >
1, we can divide the problem into two instances of the same problem: to compute the sum of the
first [n/2] numbers and to compute the sum of the remaining [n/2] numbers. (Of course, if n = 1,
we simply return a0 as the answer.) Once each of these two sums is computed by applying the
same method recursively, we can add their values to get the sum in question:

a0 + . . . + an−1 = (a0 + . . . + a[n/2]−1) + (a[n/2] + . . . + an−1).

Example: Calculate sum of the following sequence of the numbers: 5, 8, 4, 6, 2, 9, 1, 7

5 8 4 6 2 9 1 7

5 8 4 6 2 9 1 7

5+8+4+6 = 23 2+9+1+7 = 19

23+19 = 42

Common problems solved using divide-and-conquer:

1. Sorting Algorithms:

 Merge Sort: Divides the list into halves, sorts them recursively, and merges the sorted halves.

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 8|Page

  Quick Sort: Chooses a pivot, partitions the list around it, and recursively sorts the sublists.

2. Searching Algorithms:

 Binary Search: Repeatedly divides the search interval in half until the target element is found.

3. Mathematical Calculations:

 Factorial: factorial(n) = n * factorial(n-1) (base case: factorial(0) = 1)

 Fibonacci Sequence: fib(n) = fib(n-1) + fib(n-2) (base cases: fib(0) = 0, fib(1) = 1)

4. Tree Traversals:

 Preorder, inorder, and postorder traversals of binary trees use divide-and-conquer to visit nodes
in a specific order.

5. Closest Pair of Points: Efficiently finds the closest pair of points in a plane using a divide-and-
conquer approach.

6. Convex Hull: Finds the convex hull of a set of points in the plane.

7. Strassen's Matrix Multiplication: Multiplies two matrices faster than the traditional algorithm for
large matrices.

8. Fast Fourier Transform (FFT): Efficiently computes the discrete Fourier transform of a sequence.

Advantages of divide-and-conquer:

 Efficient for many problems: Often leads to algorithms with lower time complexity than other
approaches.
 Easier to understand and implement: Divide-and-conquer algorithms often have a clear structure
and recursive logic.
 Amenable to parallelization: Subproblems can be solved independently, making them suitable
for parallel computing.

Disadvantages of divide-and-conquer:

 Can be less efficient for small problems: Overhead of function calls and recursion can make
them less efficient for very small problem sizes.
 Can be memory-intensive: Recursion can consume more memory due to stack frames.

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 9|Page

e) Backtracking

As the name suggests we backtrack to find the solution. We start with one possible move out of
many available moves and try to solve the problem if we are able to solve the problem with the
selected move then we will print the solution else we will backtrack and select some other move
and try to solve it. If none of the moves work out, we will claim that there is no solution for the
problem.

This algorithm design technique can be described as an organized exhaustive search which often
avoids searching all possibilities. It is generally suitable for solving problems where a potentially
large but finite number of solutions have to be inspected.

Example: A practical example of a backtracking algorithm is the problem of arranging furniture in

a new house. There are many possibilities; each piece of furniture is placed in some part of the
room. If all the furniture is placed and the owner is happy, then the algorithm terminates. If we
reach a point where all subsequent placement of furniture is undesirable, we have to undo the last
step and try an alternative. Of course, this might force another undo, and so forth. If we find that
we undo all possible first steps, then there is no placement of furniture that is satisfactory.
Otherwise, we eventually terminate with a satisfactory arrangement.

Notice that although this algorithm is essentially brute force, it does not try all possibilities
directly. For instance, arrangements that consider placing the sofa in the kitchen are never tried.
Many other bad arrangements are discarded early, because an undesirable subset of the
arrangement is detected. The elimination of a large group of possibilities in one step is known as
pruning.

Common problems solved using backtracking:

1. N-Queens Problem: Placing N queens on an NxN chessboard so that no two queens attack each
other.
2. Sudoku Solver: Filling a 9x9 Sudoku grid with digits 1-9 such that each row, column, and 3x3
subgrid contains each digit only once.
3. Maze Solving: Finding a path from a starting point to an ending point in a maze.
4. Knapsack Problem: Choosing items to fill a knapsack with a maximum weight
capacity, maximizing the total value of the items.
5. Graph Coloring: Assigning colors to vertices of a graph so that no two adjacent vertices have
the same color.
6. Hamiltonian Cycle Problem: Finding a cycle in a graph that visits every vertex exactly once.
7. Travelling Salesman Problem: Finding the shortest possible route that visits each city in a list
exactly once and returns to the origin city.
8. Subset Sum Problem: Determining whether a subset of numbers in a set adds up to a given
target value.

Advantages of backtracking:

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 10 | P a g e

 Can solve complex combinatorial problems: Well-suited for problems with many possible
combinations or arrangements.
 Finds all solutions or the optimal solution: Can be used to find all valid solutions or the best
solution, depending on the problem.
 Easy to implement: Backtracking algorithms often have a simple structure and can be implemented
using recursion.

Disadvantages of backtracking:

 Can be inefficient for large problems: The number of possible paths to explore can grow
exponentially with problem size, leading to slow performance.
 Can be memory-intensive: Storing the state of the search tree for backtracking can consume
significant memory.

f) Pattern matching and string/text algorithms:

Pattern matching algorithm design involves finding occurrences of specific patterns within larger
data sets. It's a fundamental technique used in various text processing, data analysis, and
computational problems.

Key features:
 Pattern: A sequence of characters, numbers, symbols, or other data elements that define the
search target.
 Text or data: The larger dataset within which the pattern is sought.
 Matching algorithms: Methods for efficiently identifying occurrences of the pattern.

Common examples of pattern matching algorithms:

 Naive String Matching:

Simplest approach, comparing the pattern with each substring of the text.
Inefficient for large texts due to its linear time complexity.

 Knuth-Morris-Pratt (KMP) Algorithm:

Efficiently handles multiple pattern occurrences without re-scanning text.
Preprocesses the pattern to create a "failure function" for faster matching.

 Boyer-Moore Algorithm:
Scans from right to left, skipping large portions of text when a mismatch occurs.
Often faster than KMP in practice, especially for longer patterns.

 Rabin-Karp Algorithm:
Uses a hash function to quickly detect potential matches.
Useful for finding patterns with potential errors or variations.

 Regular Expression Matching:

Employs regular expressions, a powerful pattern language for complex patterns.

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 11 | P a g e

 Widely used in text processing, search engines, and programming languages.

Applications of pattern matching:

 Text Search: Finding words, phrases, or specific patterns in text documents.

 DNA Sequence Analysis: Locating specific gene sequences or patterns in DNA data.
 Image Processing: Detecting objects, shapes, or features in images.
 Network Security: Identifying malicious code or intrusion signatures in network traffic.
 Natural Language Processing: Extracting information, classifying text, and performing
tasks like sentiment analysis or machine translation.
 Data Mining: Discovering patterns and relationships in large datasets.
 Bioinformatics: Analysing protein structures, gene expression data, and other biological
data.
 Compiler Design: Identifying patterns in programming code for parsing and code
generation.

Example: Here is an example of pattern matching using regular expressions that ginds words that
start with a vowel:

\b[aeiouAEIOU]\w+\b

This regular expression matches words that start with a vowel (lowercase or uppercase), followed
by one or more word characters.

g) Randomized Algorithm

A randomized algorithm can be defined as one that receives, in addition to its input, a stream of
random bits that it can use in the course of its action for the purpose of making random choices. A
randomized algorithm may give different results when applied to the same input in different runs. It
follows that the execution time of a randomized algorithm may vary from one run to another when
applied to the same input. By now, it is recognized that, in a wide range of applications, randomization
is an extremely important tool for the construction of algorithms. There are two main advantages that
randomized algorithms often have. First, often the execution time or space requirement of a
randomized algorithm is smaller than that of the best deterministic algorithm that we know of for the
same problem. Second, if we look at the various randomized algorithms that have been invented so far,
we find that invariably they are extremely simple to comprehend and implement. The following is a
simple example of a randomized algorithm.

Example: Random Number Generator: Suppose we only need to flip a coin; thus, we must generate a
0 (for heads) or 1 (for tails) randomly.

2.2. Algorithm Analysis

Algorithm analysis: The process of determining, as precisely as possible, how much of various
resources (such as time and memory) an algorithm consumes when it executes.

The term “Analysis of algorithms” was coined by Donald Knuth.

It is very common for beginning computer science students to compare their programs with one
another. You may also have noticed that it is common for computer programs to look very similar,

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 12 | P a g e

 especially the simple ones. An interesting question often arises. When two programs solve the same
problem but look different, is one program better than the other?

Once an algorithm is given for a problem and decided (somehow) to be correct, an important step is to
determine how much in the way of resources, such as time or space, the algorithm will require. An
algorithm that solves a problem but requires a year is hardly of any use. Likewise, an algorithm that
requires a gigabyte of main memory is not (currently) useful.

Why we need to analyze algorithm?

There are often many different algorithms which can be used to solve the same problem. Thus, it
makes sense to develop techniques that allow us to:
 Compare different algorithms with respect to their efficiency
 Choose the most efficient algorithm for the problem

2.3. Measuring the Efficiency of Algorithms

Some algorithms consume an amount of time or memory that is below a threshold of tolerance. For
example, most users are happy with any algorithm that loads a file in less than one second. For such
users, any algorithm that meets this requirement is as good as any other. Other algorithms take an
amount of time that is totally impractical (say, thousands of years) with large data sets. We can’t use
these algorithms, and instead need to find others, if they exist, that perform better.

When choosing algorithms, we often have to settle for a space/time tradeoff. An algorithm can be
designed to gain faster run times at the cost of using extra space (memory), or the other way around.
Some users might be willing to pay for more memory to get a faster algorithm, whereas others would
rather settle for a slower algorithm that economizes on memory. Memory is now quite inexpensive for
desktop and laptop computers, but not yet for miniature devices.

In any case, because efficiency is a desirable feature of algorithms, it is important to pay attention to
the potential of some algorithms for poor performance. In this section, we consider several ways to
measure the efficiency of algorithms.

We usually want our algorithms to possess several qualities. After correctness, by far the most
important is efficiency. In fact, there are two kinds of algorithm efficiency: time efficiency, indicating
how fast the algorithm runs, and space efficiency, indicating how much extra memory it uses.

2.3.1. Measuring the Run Time of an Algorithm (Empirical/practical Analysis)

One way to measure the time cost of an algorithm is to use the computer’s clock to obtain an actual
run time. This process, called benchmarking or profiling, starts by determining the time for several
different data sets of the same size and then calculates the average time. Next, similar data are
gathered for larger and larger data sets. After several such tests, enough data are available to predict
how the algorithm will behave for a data set of any size.

In empirical analysis to measure how much time an algorithm takes to run, we must code it up in a
program. Empirical analysis of algorithm is based on executing the algorithm on a computer. We will
only have measurements of the running times of various programs written by particular programmers
in particular languages run on certain machines with certain operating systems supporting particular
loads.

General Plan for the Empirical Analysis of Algorithm Time Efficiency

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 13 | P a g e

1. Understand the experiment’s purpose.
2. Decide on the efficiency metric M to be measured and the measurement unit (an operation count
vs. a time unit).
3. Decide on characteristics of the input sample (its range, size, and so on).
4. Prepare a program implementing the algorithm (or algorithms) for the experimentation.
5. Generate a sample of inputs.
6. Run the algorithm (or algorithms) on the sample’s inputs and record the data observed.
7. Analyze the data obtained.

Example:

Suppose that we are given three algorithms (A, B and C) that solve the same problem, with
complexities O(n), O(n2), and O(2n), respectively. Measurement shows that their actual running times
on a particular processor are [Link] seconds, 0.0ln2 seconds, and 0.0001 * 2n seconds, respectively,
where n is the number of data items to be processed.

The following table shows the largest values of n for which the problem can be solved in a second, a
minute, and an hour:

Algorithm Running time Maximum n in 1 Maximum n in 1 Maximum n in 1

(seconds) second minute hour
A 0.1*n 10 600 36000
B 0.01*n2 10 77 600
C 0.0001 * 2n 9 15 21

In one second, all three algorithms can process the same amount of data (by coincidence). But there
the similarity ends. In one minute, Algorithm A can process by far the most data, and Algorithm C the
least. If an hour is allowed, Algorithm A is out of sight!

How much difference does it make if we use a processor that is ten times faster? This reduces each
algorithm's running time by a factor of ten. The effects are as follows:

Algorithm Running time Maximum n in 1 Maximum n in 1 Maximum n in 1

(seconds) second minute hour
A 0.01n 100 6000 360000
2
B 0.001n 31 244 1897
n
C 0.00001 * 2 13 19 25

Ironically, Algorithm A (already the fastest) benefits the most, and Algorithm C (already the slowest)
benefits the least, from using the faster processor! Algorithm A can now process ten times as much
data in any given time, Algorithm B about three times as much data, and Algorithm C only three extra
data items.

Even if we handicap Algorithm A by leaving it to run on the slower processor, in as little as a minute it
beats Algorithm B and outclasses Algorithm C.

From a practical perspective a measure of the efficiency of an algorithm is achieved by analyzing the
efficiency with which its implementation utilizes a computer’s time and space. By space efficiency,
we mean the amount of memory an algorithm consumes when it runs. As for time efficiency, at first

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 14 | P a g e

glance one would expect this to mean the amount of time it takes the algorithm to execute; however,
there are several reasons or factors why such an absolute/empirical measure is not appropriate:

 The execution time of an algorithm is sensitive to the amount of data (Input size) that it must
manipulate and typically grows as the amount of data increases.
 The execution times for an algorithm when run with the same data set on two different
computers may differ because of the execution speeds f the processors.
 Depending on how an algorithm is implemented on a particular computer (choice of
programming language, use of compiler or interpreter, and so forth), one implementation of an
algorithm may run faster than another, even on the same computer and with the same data set.

2.3.2. Counting Instructions (Theoretical Analysis or Mathematical representation)

In assessing the efficiency of an algorithm’s run time we want to remove all implementation
considerations from our analysis and focus on those aspects of the algorithm that most critically affect
this execution time. We noted that one of these is the number of data items that algorithm manipulates.
Typically, the rest of the analysis consists of trying to determine how often a critical operation (e.g., a
comparison, data interchange, or addition or multiplications of values) or sequence of such operations
gets performed in manipulating these data items. This count, expressed as a function of a variable n
that provides an indicator of the size of the set of data items, is what represents the “running time” of
the algorithm.

Another technique used to estimate the efficiency of an algorithm is to count the instructions executed
with different problem sizes. These counts provide a good predictor of the amount of abstract work
performed by an algorithm, no matter what platform the algorithm runs on. Keep in mind, however,
that when you count instructions, you are counting the instructions in the high-level code in which the
algorithm is written, not instructions in the executable machine language program.

When analyzing an algorithm in this way, you distinguish between two classes of instructions:
a. Instructions that execute the same number of times regardless of the problem size
b. Instructions whose execution count varies with the problem size

Here, the complexity time is related to the number of steps/operations. Complexity time can be
determined by:
a. Count the number of steps and then find the class of complexity. Or
b. Find the complexity time for each steps and then count the total.

Let us consider the following problem.

Example:

The holiday season is approaching and a gift shop is expecting sales to be double or even triple the
regular amount. They have hired extra delivery people to deliver the packages on time. The company
calculates the shortest distance from the shop to a particular destination and hands the route to the
driver. Suppose that 50 packages are to be delivered to 50 different houses. The shop, while making
the route, finds that the 50 houses are one mile apart and are in the same area. (See the Figure below,
in which each dot represents a house and the distance between houses is 1 mile.)

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 15 | P a g e

Case 1:
To deliver 50 packages to their destinations, one of the drivers picks up all 50 packages, drives one
mile to the first house and delivers the first package. Then he drives another mile and delivers the
second package, drives another mile and delivers the third package, and so on. The Figure below
illustrates this delivery scheme.

It now follows that using this scheme, the distance driven by the driver to deliver the packages is:
1 + 1 + 1 + ... + 1 = 50 miles
Therefore, the total distance traveled by the driver to deliver the packages and then getting back to the
shop is:
50 + 50 = 100 miles

Case 2:
Another driver has a similar route to deliver another set of 50 packages. The driver looks at the route
and delivers the packages as follows: The driver picks up the first package, drives one mile to the first
house, delivers the package, and then comes back to the shop. Next, the driver picks up the second
package, drives 2 miles, delivers the second package, and then returns to the shop. The driver then
picks up the third package, drives 3 miles, delivers the package, and comes back to the shop. The
Figure below illustrates this delivery scheme.

The driver delivers only one package at a time. After delivering a package, the driver comes back to
the shop to pick up and deliver the second package. Using this scheme, the total distance traveled by
this driver to deliver the packages and then getting back to the store is:
2 . (1 + 2 + 3 +… + 50) = 2550 miles

Now suppose that there are n packages to be delivered to n houses, and each house is one mile apart
from each other, as shown in Figure 1-1. If the packages are delivered using the first scheme, the
following equation gives the total distance traveled:

1 + 1 + … + 1 + n = 2n (2.1)

If the packages are delivered using second method (case2), the distance traveled is:

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 16 | P a g e

 2. (1 + 2 + 3 + … + n) = 2 > (n (n +1) / 2 ) = n2 + n (2.2)

While analyzing a particular algorithm, we usually count the number of operations performed by the
algorithm. We focus on the number of operations, not on the actual computer time to execute the
algorithm. This is because a particular algorithm can be implemented on a variety of computers and
the speed of the computer can affect the execution time. However, the number of operations performed
by the algorithm would be the same on each computer. Let us consider the following examples.

Example: The maximum element in an array can be looked up using a simple piece of code

int M = A[ 0 ];

for ( i = 0; i < n; ++i )

{
if ( A[ i ] >= M )
{
M = A[ i ];
}
}

Now, the first thing we'll do is count how many fundamental instructions this piece of code executes.
We will only do this once and it won't be necessary as we develop our theory. As we analyze this
piece of code, we want to break it up into simple instructions; things that can be executed by the CPU
directly - or close to that. We'll assume our processor can execute the following operations as one
instruction each:

 Assigning a value to a variable

 Looking up the value of a particular element in an array
 Comparing two values
 Incrementing a value
 Basic arithmetic operations such as addition and multiplication

We'll assume branching (the choice between if and else parts of code after the if condition has been
evaluated) occurs instantly and won't count these instructions. In the above code, the first line of code
is:

int M = A[ 0 ];

This requires 2 instructions: One for looking up A[ 0 ] and one for assigning the value to M (we're
assuming that n is always at least 1). These two instructions are always required by the algorithm,
regardless of the value of n. The for loop initialization code also has to always run. This gives us two
more instructions; an assignment and a comparison:

i = 0;
i < n;

These will run before the first for loop iteration. After each for loop iteration, we need two more
instructions to run, an increment of i and a comparison to check if we'll stay in the loop:

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 17 | P a g e

++i;
i < n;

So, if we ignore the loop body, the number of instructions this algorithm needs is 4 + 2n. That is, 4
instructions at the beginning of the for loop and 2 instructions at the end of each iteration of which we
have n. We can now define a mathematical function f( n ) that, given an n, gives us the number of
instructions the algorithm needs. For an empty for body, we have f( n ) = 4 + 2n.

Now, looking at the for body, we have an array lookup operation and a comparison that happen
always:

if ( A[ i ] >= M ) { ...

That's two instructions right there. But the if body may run or may not run, depending on what the
array values actually are. If it happens to be so that A[ i ] >= M, then we'll run these two additional
instructions — an array lookup and an assignment:

M = A[ i ]

But now we can't define an f( n ) as easily, because our number of instructions doesn't depend solely
on n but also on our input. For example, for A = [ 1, 2, 3, 4 ] the algorithm will need more
instructions than for A = [ 4, 3, 2, 1 ]. When analyzing algorithms, we often consider the worst-
case scenario. What's the worst that can happen for our algorithm? When does our algorithm need the
most instructions to complete? In this case, it is when we have an array in increasing order such as A =
[ 1, 2, 3, 4 ]. In that case, M needs to be replaced every single time and so that yields the most
instructions. Computer scientists have a fancy name for that and they call it worst-case analysis; that's
nothing more than just considering the case when we're the most unlucky. So, in the worst case, we
have 4 instructions to run within the for body, so we have f( n ) = 4 + 2n + 4n = 6n + 4. This function
f, given a problem size n, gives us the number of instructions that would be needed in the worst-case.

Example:

Consider the following piece of code...

int sum(int A[ ], int n)

{
int sum = 0, i;
for(i = 0; i < n; i++)
sum = sum + A[i];
return sum;
}

For the above code, time complexity can be calculated as follows...

int sum(int A[ ], int n) Cost Repetition Total

Time require for line (unit) No. of times executed Total time required in worst case
{
int sum = 0, i; 1 1 1
for(i = 0; i < n; i++) 1+1+1 1+(n+1)+n 2n+2
sum = sum + A[i]; 2 n 2n

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 18 | P a g e

 return sum; 1 1 1
}
Total Time Required 4n+4

In above calculation
Cost is the amount of computer time required for a single operation in each line.
Repetition is the amount of computer time required by each operation for all its repetitions.
Total is the amount of computer time required by each operation to execute.

So above code requires '4n+4' Units of computer time to complete the task. Here the exact time is not
fixed. And it changes based on the n value. If we increase the n value then the time required also
increases linearly.

Totally it takes '4n+4' a unit of time to complete its execution.

Example:

Consider the following algorithm. (Assume that all variables are properly declared.)

cout << "Enter two numbers"; //Line 1

cin >> num1 >> num2; //Line 2
if (num1 >= num2) //Line 3
max = num1; //Line 4
else //Line 5
max = num2; //Line 6
cout << "The maximum number is: " << max << endl; //Line 7

Line 1 has one operation, <<; Line 2 has two operations; Line 3 has one operation, >=; Line 4 has one
operation, =; Line 6 has one operation; and Line 7 has three operations. Either Line 4 or Line 6
executes. Therefore, the total number of operations executed in the preceding code is 1 + 2 + 1 + 1 + 3
= 8. In this algorithm, the number of operations executed is fixed.

Example:

Consider the following algorithm:

cout << "Enter positive integers ending with -1" << endl; //Line 1
count = 0; //Line 2
sum = 0; //Line 3
cin >> num; //Line 4
while (num != -1) //Line 5
{
sum = sum + num; //Line 6
count++; //Line 7
cin >> num; //Line 8
}
cout << "The sum of the numbers is: "<< sum << endl; //Line 9
if (count != 0) //Line 10
average = sum / count; //Line 11
else //Line 12

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 19 | P a g e

 average = 0; //Line 13
cout << "The average is: " << average << endl; //Line 14

This algorithm has five operations (Lines 1 through 4) before the while loop. Similarly, there are nine
or eight operations after the while loop, depending on whether Line 11 or Line 13 executes. Line 5 has
one operation, and four operations within the while loop (Lines 6 through 8). Thus, Lines 5 through 8
have five operations. If the while loop executes 10 times, these five operations execute 10 times. One
extra operation is also executed at Line 5 to terminate the loop. Therefore, the number of operations
executed is 51 from Lines 5 through 8.

If the while loop executes 10 times, the total number of operations executed is:

10 . 5 + 1 + 5 + 9 or 10 . 5 + 1 + 5 + 8

that is,

10 . 5 + 15 or 10 . 5 + 14

We can generalize it to the case when the while loop executes n times. If the while loop executes n
times, the number of operations executed is:

5n + 15 or 5n + 14

In these expressions, for very large values of n, the term 5n becomes the dominating term and the
terms 15 and 14 become negligible.

2.4. Space Complexity

The better the time complexity of an algorithm is, the faster the algorithm will carry out his work in
practice. Apart from time complexity, its space complexity is also important. This is essentially the
number of memory cells which an algorithm needs. A good algorithm keeps this number as small as
possible, too.

There is often a time-space-tradeoff involved in a problem, that is, it cannot be solved with few
computing time and low memory consumption. One then has to make a compromise and to exchange
computing time for memory consumption or vice versa, depending on which algorithm one chooses
and how one parameterizes it.

Space complexity of an algorithm can be defined as follows:

Total amount of computer memory required by an algorithm to complete its execution is called as
space complexity of that algorithm.

When we design an algorithm to solve a problem, it needs some computer memory to complete its
execution. For any algorithm, memory is required for the following purposes.

 Memory required to store program instructions

 Memory required to store constant values
 Memory required to solve variable values
 And for few other things

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 20 | P a g e

To calculate the space complexity, we must know the memory required to store different data type
values (according to the compiler). For example, the C programming language compiler requires the
following:

 2 bytes to store integer value,

 4 bytes to store floating value,
 1 byte to store character value,
 8 or 8 bytes to store double value

Example:

Consider the following piece of code...

int square(int a)
{
return a*a;
}

In above piece of code, it requires 2 bytes of memory to store variable ‘a’ and another 2 bytes of
memory is used for return value.

That means, totally it requires 4 bytes of memory to complete its execution. And this 4 bytes of
memory is fixed for any input value of 'a'. This space complexity is said to be Constant Space
Complexity.

If any algorithm requires a fixed amount of space for all input values then that space complexity is
said to be Constant Space Complexity.

Example:

Consider the following piece of code...

int sum(int A[], int n)

{
int sum = 0, i;
for(i = 0; i < n; i++)
sum = sum + A[i];
return sum;
}

In above piece of code it requires

'n*2' bytes of memory to store array variable 'a[]'

2 bytes of memory for integer parameter 'n'
4 bytes of memory for local integer variables 'sum' and 'i' (2 bytes each)
2 bytes of memory for return value.

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 21 | P a g e

 That means, totally it requires '2n+8' bytes of memory to complete its execution. Here, the
amount of memory depends on the input value of 'n'. This space complexity is said to be Linear
Space Complexity.

If the amount of space required by an algorithm is increased with the increase of input value, then that
space complexity is said to be Linear Space Complexity.

2.5. Complexity Analysis

In this section, we develop a method of determining the efficiency of algorithms that allows us to rate
them independently of platform-dependent timings or impractical instruction counts. This method,
called complexity analysis, entails reading the algorithm and using pencil and paper to work out some
simple algebra.

2.5.1. Rates of growth (Function of growth rates) or (Order of growth)

In analysis of algorithms, it is not important to know exactly how many operations an algorithm does.
Of greater concern is the rate of increase in operations for an algorithm to solve a problem as the size
of the problem increases. This is referred to as the rate of growth of the algorithm. What happens with
small sets of input data is not as interesting as what happens when the data set gets large.

Because we are interested in general behavior, we just look at the overall growth rate of algorithms,
not at the details.

Common Functions used in analysis

A. The Constant Function f(n) = c

For any argument n, the constant function f(n) assigns the value C. It doesn't matter what the
input size n is, f(n) will always be equal to the constant value C. The most fundamental
constant function is f(n) = 1, and this is the typical constant function that is used in this course.

The constant function is useful in algorithm analysis, because it characterizes the number of
steps needed to do a basic operation on a computer, like adding two numbers, assigning a value
to some variable, or comparing two numbers. Executing one instruction a fixed number of
times also needs constant time only.

Constant algorithm does not depend on the input size.

Examples: arithmetic calculation, comparison, variable declaration, assignment statement,

invoking a method or function. Count++;

B. The Logarithm Function f(n)= logn

It is one of the interesting and surprising aspects of the analysis of data structures and
algorithms. The general form of a logarithm function is f(n) = logbn, for some constant b > 1.
This function is defined as follows:

x = logbn, if and only if bx = n

The value b is known as the base of the logarithm. Computing the logarithm function for any

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 22 | P a g e

 integer n is not always easy, but we can easily compute the smallest integer greater than or
equal to logbn, for this number is equal to the number of times we can divide n by b until we get
a number less than or equal to 1. For example, log327 is 3, since 27/3/3/3 = 1. Likewise, log212 =
4, since 12/2/2/2/2 = 0.75 <= 1.

The base-two approximating arises in the algorithm analysis, since a common operation in
many algorithms is to repeatedly divide an input in half. In fact, the most common base for the
logarithm in computer science is 2. We typically leave it off when it is 2.

Logarithm function gets slightly slower as n grows. Whenever n doubles, the running time
increases by a constant.

Examples: binary search.

C. The Linear Function f(n) = n

Another simple yet important function is linear function. Given an input value n, the linear
function f assigns the value n itself. This function arises in an algorithm analysis any time we
do a single basic operation for each of n elements. For example, comparing a number x to each
element of an array of size n will require n comparisons. The linear function also represents the
best running time we hope to achieve for any algorithm that processes a collection of n inputs.

Whenever n doubles, so does the running time.

Example: print out the elements of an array of size n.

D. The N-Log-N Function f(n) =nlogn

This function grows a little faster than the linear function and a lot slower than the quadratic
function (n2). If we can improve the running time of solving some problem from quadratic to
NLog-N, we will have an algorithm that runs much faster in general. It scales to a huge
problem, since whenever n doubles, the running time more than doubles.

Example: merge sort, which will be discussed in chapter 8.

E. The Quadratic Function f(n) = n2

It appears a lot in the algorithm analysis, since there are many algorithms that have nested
loops, where the inner loop performs a linear number of operations and the outer loop is
performed a linear number of times. In such cases, the algorithm performs n*n = n2 operations.
The quadratic function can also be used in the context of nested loops where the first iteration
of a loop uses one operation, the second uses two operations, the third uses three operations,
and so on. That is, the number of operations is 1 + 2 + 3 + ... + (n-1) + n.

For any integer n >= 1, we have 1 + 2 + 3 + ... + (n-1) + n = n*(n+1) / 2.

Quadratic algorithms are practical for relatively small problems. Whenever n doubles, the
running time increases fourfold.

Example: some manipulations of the n by n array.

F. The Cubic Function f(n) = n3
This function appears less frequently in the context of the algorithm analysis than the constant,

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 23 | P a g e

 linear, and quadratic functions. It's practical for use only on small problems. Whenever n
doubles, the running time increases eightfold.

Example: n by n matrix multiplication.

G. The Exponential Function f(n) = bn

In this function, b is a positive constant, called the base, and the argument n is the exponent.
In the algorithm analysis, the most common base for the exponential function is b = 2. For
instance, if we have a loop that starts by performing one operation and then doubles the
number of operations performed with each iteration, then the number of operations performed
in the nth iteration is 2n.

Exponential algorithm is usually not appropriate for practical use.

Example: Towers of the Hanoi.

2.5.2. Comparing Growth Rates

The growth rate for an algorithm is the rate at which the cost of the algorithm grows as the size
of its input grows. Problem size depends on the particular problem:

Example: number of nodes in a linked-list, number of disks in the tower of Hanoi Problem,
size of an array, number of elements in a stack, etc.

The important thing is to find out how quickly the time of an algorithm grows as a function of
the problem size. This is called an algorithm's growth rate.

Figure 2.1: Growth rates

Order of increasing complexity

O(1) < O(logxn) < O(n) < O(n log2n) < O(n2) < O(n3) < O(2n)

2.5.3. Worst-Case, Best-Case, and Average-Case Efficiencies

Worst case complexity W(n): The maximum number of basic operations performed by an algorithm

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 24 | P a g e

for any input of size n.
– This gives an upper bound for the time complexity of an algorithm.
– Normally, we try to find worst-case behavior of an algorithm.

Best case complexity B(n): The minimum number of basic operations performed by an algorithm for
any input of size n.
– The best case behavior of an algorithm is NOT so useful.

Average case complexity A(n): The average number of basic operations performed by an algorithm
for all inputs of size n, given assumptions about the characteristics of inputs of size n.

– Sometimes, it is difficult to find the average-case behavior of an algorithm.

– We have to look at all possible data organizations of a given size n, and their distribution
probabilities of these organizations.

2.5.4. Asymptotic Analysis and Notations

The notation was first introduced by number theorist Paul Bachmann in 1894, in the second volume of
his book Analytische Zahlentheorie ("analytic number theory”). The notation was popularized in the
work of number theorist Edmund Landau; hence it is sometimes called a Landau symbol.

It was popularized in computer science by Donald Knuth, who (re)introduced the related Omega and
Theta notations. Knuth also noted that the (then obscure) Omega notation had been introduced by
Hardy and Littlewood under a slightly different meaning, and proposed the current definition.

In general, each basic step in a pseudo-code description or a high-level language implementation

corresponds to a small number of primitive operations (except for function calls, of course). Thus, we
can perform a simple analysis of an algorithm written in pseudo-code that estimates the number of
primitive operations executed up to a constant factor, by pseudo-code steps (but we must be careful,
since a single line of pseudo-code may denote a number of steps in some cases).

Asymptotic notation of an algorithm is a mathematical representation of its complexity.

Primitive Operations:
As noted above, experimental analysis is valuable, but it has its limitations. If we wish to analyze a
particular algorithm without performing experiments on its running time, we can perform an analysis
directly on the high-level pseudo-code instead. We define a set of primitive operations such as the
following:
• Assigning a value to a variable
• Calling a function
• Performing an arithmetic operation (for example, adding two numbers)
• Comparing two numbers
• Indexing into an array
• Following an object reference
• Returning from a function

Counting Primitive Operations

Specifically, a primitive operation corresponds to a low-level instruction with an execution time that is
constant. Instead of trying to determine the specific execution time of each primitive operation, we
simply count how many primitive operations are executed, and use this number t as a measure of the
running time of the algorithm.

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 25 | P a g e

 As pointed out in the previous section, the efficiency analysis framework concentrates on the order of
growth of an algorithm’s basic operation count as the principal indicator of the algorithm’s efficiency.
To compare and rank such orders of growth, computer scientists use three notations:
a. O (big oh),
b. Ω (big omega), and
c. Θ (big theta).

[Link]. The “Big-Oh” Notation (O)

Big - Oh notation is used to define the upper bound of an algorithm in terms of Time Complexity.

That means Big - Oh notation always indicates the maximum time required by an algorithm for all
input values. That means Big - Oh notation describes the worst case of an algorithm time complexity.

Definition: Let f (n) and g(n) be functions mapping nonnegative integers to real numbers. We say that
f (n) is O(g(n)) if there is a real constant c > 0 and an integer constant n0 ≥ 1 such that

f (n) ≤ cg(n), for n ≥ n0.

This definition is often referred to as the “big-Oh” notation, for it is sometimes pronounced as “ f (n) is
big-Oh of g(n).” Alternatively, we can also say “ f (n) is order of g(n).” (This definition is illustrated
in Figure 2.2.)

Figure 2.2: The “big-Oh” notation. The function f (n) is O(g(n)), since f (n) ≤ c ·g(n) when n ≥ n0.

Example: The function 8n−2 is O(n).

Justification: By the big-Oh definition, we need to find a real constant c>0 and an integer constant n0
≥ 1 such that 8n−2 ≤ cn for every integer n ≥ n0. It is easy to see that a possible choice is c = 8 and n0
= 1. Indeed, this is one of infinitely many choices available because any real number greater than or
equal to 8 works for c, and any integer greater than or equal to 1 works for n0.

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 26 | P a g e

The big-Oh notation allows us to say that a function f (n) is “less than or equal to” another function
g(n) up to a constant factor and in the asymptotic sense as n grows toward infinity. This ability comes
from the fact that the definition uses “≤” to compare f (n) to a g(n) times a constant, c, for the
asymptotic cases when n≥n0.

Some Properties of the Big-Oh Notation

The big-Oh notation allows us to ignore constant factors and lower order terms and focus on the main
components of a function that affect its growth.

Example: 5n4 +3n3+2n2 +4n+1 is O(n4).

Justification: Note that 5n4+3n3+2n2+4n+1≤ (5+3+2+4+1)n4 = cn4,
for c = 15, when n ≥ n0 = 1.

In fact, we can characterize the growth rate of any polynomial function.

Proposition: If f (n) is a polynomial of degree d, that is,
f (n) = a0 +a1n+···+adnd , and ad > 0, then f (n) is O(nd).
Justification: Note that, for n ≥ 1, we have 1 ≤ n ≤ n2 ≤ ··· ≤ nd; hence,
a0+a1n+a2n2+···+adnd ≤ (a0 +a1+a2+···+ad)nd .
Therefore, we can show f (n) is O(nd) by defining c=a0+a1+···+ad and n0 =1.

Example: 5n2 +3nlog n+2n+5 is O(n2).

Justification: 5n2+3nlog n+2n+5 ≤ (5+3+2+5) n2 = cn2, for c=15, when n ≥ n0 = 2 (note that nlog n is
zero for n = 1).

Example: 20n3 +10nlog n + 5 is O(n3).

Justification: 20n3 +10nlog n+5 ≤ 35n3, for n ≥ 1.

Example: 3log n+2 is O(logn).

Justification: 3logn+2 ≤ 5log n, for n ≥ 2. Note that logn is zero for n = 1.
That is why we use n ≥ n0 = 2 in this case.

Example: 2n+2 is O(2n).

Justification: 2n+2 = 2n22 = 4 ·2n; hence, we can take c = 4 and n0 = 1 in this case.

Example: 2n+100log n is O(n).

Justification: 2n+100log n≤ 102n, for n ≥n0 = 2; hence, we can take c= 102 in this case.

[Link]. Big-Omega (Ω)

Big - Omega notation is used to define the lower bound of an algorithm in terms of Time
Complexity.

That means Big - Omega notation always indicates the minimum time required by an algorithm for all
input values. That means Big - Omega notation describes the best case of an algorithm time
complexity.

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 27 | P a g e

Just as the big-Oh notation provides an asymptotic way of saying that a function is “less than or equal
to” another function, the following notations provide an asymptotic way of saying that a function
grows at a rate that is “greater than or equal to” that of another.

Definition: Let f (n) and g(n) be functions mapping nonnegative integers to real numbers. We say that
f (n) is Ω (g(n)) (pronounced “ f (n) is big-Omega of g(n)”) if g(n) is O( f (n)), that is, there is a real
constant c > 0 and an integer constant n0 ≥ 1 such that
f (n) ≥ cg(n), for n ≥ n0.

This definition allows us to say asymptotically that one function is greater than or equal to another, up
to a constant factor.

Figure 2.3: Big-omega notation: t (n) ϵ Ω (g(n)).

Example: 3nlog n+2n is Ω (nlog n).

Justification: 3nlog n+2n ≥ 3nlog n, for n ≥ 2.

Example: 3n+2 is Ω (n).

Justification: 3n+2 ≥ c n, for c>=1and n ≥ 1.

[Link]. Big-Theta (Θ)

Big - Theta notation is used to define the average bound of an algorithm in terms of Time
Complexity.

That means Big - Theta notation always indicates the average time required by an algorithm for all
input values. That means Big - Theta notation describes the average case of an algorithm time
complexity.

Definition: In addition, there is a notation that allows us to say that two functions grow at the same
rate, up to constant factors. We say that f (n) is Θ (g(n)) (pronounced “ f (n) is big-Theta of g(n)”) if f

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 28 | P a g e

 (n) is O(g(n)) and f (n) is Ω (g(n)), that is, there are real constants C1 > 0 and C2 > 0, and an integer
constant n0 ≥ 1 such that

C1g(n) ≤ f (n) ≤ C2g(n), for n ≥ n0.

Example: 3nlog n+4n+5logn is Θ (nlog n).

Justification: 3nlog n ≤ 3nlog n+4n+5logn ≤ (3+4+5)nlogn for n ≥ 2.

Example: 3n2+7n+8 is Θ (n2).

Justification: 3n2 ≤ 3n2+7n+8 ≤ (3+7+8)n2 for n ≥ 1.

2.6. General rules to analyze algorithm

RULE 1-LOOPS (for, while, do-while):

The running time of a for loop is at most the running time of the statements inside the loop (including
tests) times the number of iterations.

RULE 2-NESTED LOOPS:

Analyze these inside out. The total running time of a statement inside a group of nested loops is the
running time of the statement multiplied by the product of the sizes of all the loops.

As an example, the following program fragment is O(n2):

for( i=0; i<n; i++ )

for( j=0; j<n; j++ )
k++;

RULE 3-CONSECUTIVE STATEMENTS:

These just add (which means that the maximum is the one that counts).

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 29 | P a g e

As an example, the following program fragment, which has O(n) work followed by O(n2) work, is also
O (n2):

for( i=0; i<n; i++)

a[i] = 0;
for( i=0; i<n; i++ )
for( j=0; j<n; j++ )
a[i] += a[j] + i + j;

RULE 4-IF/ELSE:

For the fragment

if( cond )
S1
else
S2

The running time of an if/else statement is never more than the running time of the test plus the larger
of the running times of S1 and S2.

RULE 5- Recursive Functions:

Recursion is a powerful technique for defining an algorithm. A procedure/function is recursive if it is,
whether directly or indirectly, defined in terms of itself. Factorial, Fibonacci number and Tower of
Hanoi are some problems that can be solved with recursion.

When a recursive algorithm calls itself, it performs the same steps over again. This repetition of steps
is somewhat similar to the effect we get when the steps are part of a loop. Indeed, often the same
algorithm can be expressed either iteratively (using loop) or recursively. For instance, the following
function is really just a simple loop and is O(N):

double factorial( int n )

{
if( n <= 1 )
return 1;
else
return n * factorial( n - 1 );
}

This example is really a poor use of recursion. When recursion is properly used, it is difficult to
convert the recursion into a simple loop structure. In this case, the analysis will involve a recurrence
relation that needs to be solved. To see what might happen, consider the following program, which
turns out to be a terrible use of recursion:

double fib( int n )

{
if( n <= 1 ) //line 1
return 1; //line 2
else
return fib( n - 1 ) + fib( n - 2 ); //line3
}

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 30 | P a g e

At first glance, this seems like a very clever use of recursion. However, if the program is coded up and
run for values of N around 40, it becomes apparent that this program is terribly inefficient. The
analysis is fairly simple. Let T(N) be the running time for the function call fib(n). If N = 0 or N = 1,
then the running time is some constant value, which is the time to do the test at line 1 and return. We
can say that T(0) = T(1) = 1 because constants do not matter. The running time for other values of N is
then measured relative to the running time of the base case. For N > 2, the time to execute the function
is the constant work at line 1 plus the work at line 3. Line 3 consists of an addition and two function
calls. Since the function calls are not simple operations, they must be analyzed by themselves. The
first function call is fib(n-1) and hence, by the definition of T, requires T(N − 1) units of time. A
similar argument shows that the second function call requires T(N−2) units of time. The total time
required is then T(N−1)+T(N−2)+2, where the 2 accounts for the work at line 1 plus the addition at line
3. Thus, for N ≥ 2, we have the following formula for the running time of fib(n):

T(N) = T(N − 1) + T(N − 2) + 2

Since fib(n) = fib(n-1) + fib(n-2), it is easy to show by induction that T(N) ≥ fib(n). (for N > 4) fib(N)
≥ (3/2)N, and so the running time of this program grows exponentially. This is about as bad as
possible. By keeping a simple array and using a for loop, the running time can be reduced
substantially.

2.7. Calculating the Running Time for a Program

Example: We begin with an analysis of a simple assignment statement to an integer variable___

a = b;
Because the assignment statement takes constant time, it is O(1).

Example: Consider a simple for loop__ ______

sum = 0;
for (i=1; i<=n; i++)
sum += n;

The first line is O(1). The for loop is repeated n times. The third line takes constant time so, the total
cost for executing the two lines making up the for loop is O(n). The cost of the entire code fragment is
also O(n)
__________________________________________________________________________________

Example: Consider several for loops, some of which are nested __

sum = 0;
for (i=1; i<=n; i++) // First for loop
for (j=1; j<=i; j++) // is a double loop (nested loop)
sum++;
for (k=0; k<n; k++) // Second for loop
A[k] = k;

This code fragment has three separate statements: the first assignment statement and the two for loops.
Again the assignment statement takes constant time; call it c1. The second for loop is just like the one
in the above Example and takes c2n = O(n) time.

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 31 | P a g e

The first for loop is a double loop and requires a special technique. We work from the inside of the
loop outward. The expression sum++ requires constant time; call it c3. Because the inner for loop is
executed i times, it has cost c3i. The outer for loop is executed n times, but each time the cost of the
inner loop is different because it costs c3i with i changing each time. You should see that for the first
execution of the outer loop, i is 1. For the second execution of the outer loop, i is 2. Each time through
the outer loop, i becomes one greater, until the last time through the loop when i = n. Thus, the total
cost of the loop is c3 times the sum of the integers 1 through n. from summation series, we know that

which is O(n2). By simplifying, O(c1 + c2n + c3n2) is simply O(n2).

_________________________________________________________________________________

Note: Not all doubly nested for lops are O(n2). The following pair of nested loops illustrates this fact:

Example: Compare the following two code fragments __

sum1 = 0;
for (k=1; k<=n; k*=2) // Do log n times
for (j=1; j<=n; j++) // Do n times
sum1++;
========================================
sum2 = 0;
for (k=1; k<=n; k*=2) // Do log n times
for (j=1; j<=k; j++) // Do k times
sum2++;

When analyzing these two code fragments, we will assume that n is a power of two. The first code
fragment has its outer for loop executed log n + 1 times because on each iteration k is multiplied by
two until it reaches n. Because the inner loop always executes n times, the total cost for the first code
fragment can be expressed as:

Note that a variable substitution takes place here to create the summation, with k = 2i. The solution for
this summation is O(n log n). In the second code fragment, the outer loop is also executed log n + 1
times. The inner loop has cost k, which doubles each time. The summation can be expressed as

Where n is assumed to be a power of two and again k = 2i. We know that this summation is simply
O(n).

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 32 | P a g e

_________________________________________________________________________________

Space Bound
Besides time, space is the other computing resource that is commonly of concern to programmers. Just
as computers have become much faster over the years, they have also received greater allotments of
memory. Even so, the amount of available disk space or main memory can be significant constraints
for algorithm designers. The analysis techniques used to measure space requirements are similar to
those used to measure time requirements. However, while time requirements are normally measured
for an algorithm that manipulates a particular data structure, space requirements are normally
determined for the data structure itself. The concepts of asymptotic analysis for growth rates on input
size apply completely to measuring space requirements.

Example: __

What are the space requirements for an array of n integers? If each integer requires c bytes, then the
array requires cn bytes, which is θ (n).

Example: ___

Imagine that we want to keep track of friendships between n people. We can do this with an array of
size n x n. Each row of the array represents the friends of an individual, with the columns indicating
who has that individual as a friend. For example, if person j is a friend of person i, then we place a
mark in column j of row i in the array. Likewise, we should also place a mark in column i of row j if
we assume that friendship works both ways. For n people, the total size of the array is θ(n2).

Speeding Up Your Programs

In practice, there is not such a big difference in running time between an algorithm whose growth rate
is O(n) and another whose growth rate is O(n log n). There is, however, an enormous difference in
running time between algorithms with growth rates of O(n log n) and O(n2).

Program design, data structure selection, and algorithm selection usually produce more dramatic
improvements. While not nearly so important as changing an algorithm to reduce its growth rate,
“code tuning” can also lead to dramatic improvements in running time. Code tuning is the art of hand
optimizing a program to run faster or require less storage. The greatest time and space improvements
come from a better data structure or algorithm. The final thought for this section is First tune the
algorithm, then tune the code.

Ins: Fikrezgy Y. CoSC2083-Data Structures and Algorithms 33 | P a g e