CSC 308: ANGORITHM AND COMPLEXITY

ANALYSIS
Dr. S. A. Bakura

January 9, 2023

1 Mathematical preliminaries
Review the following Mathematical topics as related to Algorithm Complex-
ity. Chapter 2 of [clifford] gives the overview of the concepts

• Set concepts and notation

• Logarithms

• Recursion

• Induction Proofs

• Summations

• Recurrence Relations

2 An algorithm
Is a step-by-step sequence of instruction that must be followed by computer
to solve a particular problem. ... more explanation needed here!

3 Algorithm Analysis
The concept of algorithm analysis is one of the foundemental concepts in
computer science. It’s a theorical approach to formally estimate the running
cost of an algorithm. So, there is nothing to fear as the course is friendly
and has a well established approaches to deal with any diffuculty that may
arises.

1
 One of the best methodology used to estimate running cost (Resource
Comsumption) of an algorthm is an Asymtotic algorithm analysis. In
this methodology an attempt is made to estimate the resource consumption
of an algorithm. It allows us to compare the relative costs of two or more
algorithms for solving the same problem. Asymptotic analysis also gives
algorithm designers a tool for estimating whether a proposed solution is
likely to meet the resource constraints for a problem before they implement
an actual program.

3.1 Motivation
The existance of some tools used to measure how fast a program runs such
as Profilers which measure running time in milliseconds and can help us
optimize our code by spotting bottlenecks. However, such tools are irrelevant
to algorithm complexity. In an algorithm complexity analysis, details such
as the implementation programming language, the hardware the algorithm
runs on, or the instruction set of the given CPU are usually ignored.
Moreover, comparing two algorithms by counting the number of milisec-
onds by each algorithm or by implementing the algorithm on actual hard-
ware does not help. It’s quite possible that a bad algorithm written in a
low-level programming language such as assembly runs much quicker than
a good algorithm written in a high-level programming language such as Java
or Python.
So, how can we compare algorithms and determine a better algorithm?
The answer is asymptotic analysis. Asymptotic analysis measures the
efficiency of an algorithm, or its implementation as a program, as the input
size becomes large. It is actually an estimating technique and does not tell
us anything about the relative merits of two programs where one is always
“slightly faster” than the other. However, asymptotic analysis has proved
useful to computer scientists who must determine if a particular algorithm
is worth considering for implementation.
The critical resource for a program is most often its running time. How-
ever, you cannot pay attention to running time alone. You must also be
concerned with other factors such as
• Space required to run the program (both main memory and disk
space).
• Speed of the computer’s CPU, bus, and peripheral hardware.
• Programming language and the quality of code generated by a partic-
ular compiler

2
 • Coding efficiency of the programmer who converts the algorithm to a
program

Ideally we would measure the running time of the algorithm under standard
benchmark conditions. However, we have no way to calculate the running
time reliably other than to run an implementation of the algorithm on some
computer. The only alternative is to use some other measure as a surrogate
for running time.

3.2 Counting Basic Operations (Complexity Analysis)

A basic operation must have the property that its time to complete does
not depend on the particular values of its operands. Adding or comparing
two integer variables are examples of basic operations in most programming
languages. Summing the contents of an array containing n integers is not,
because the cost depends on the value of n (i.e., the size of the input).
The maximum element in an array can be looked up using a simple piece
of code such as this piece of Javascript code. Given an input array A of size
n:

Algorithm 1 Find the Maximum element in an Array

1: var M = A[0];
2: f or(var i = 0; i < n; + + i){
3: if (A[i] >= M ){
4: M = A[i];
5: }
6: }

Now, the first thing we’ll do is count how many basic operations this piece
of code executes. 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

3
 • 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:
var M = A[ 0 ];
This requires 2 instructions: One for looking up A[ 0 ] and one for assign-
ing 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:
++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.
Worst-case analysis in side the for body
Looking at the for body; we have two basic operation: an array lookup op-
eration and a comparison that happen always.
if ( A[ i ] >= M ){ ...

if the above conditionis true, then the two additional instructions (M =

A[ i ]) — an array lookup and an assignment inside the if statement will
run otherwise it won’t. When analyzing algorithms, we often consider the
worst-case scenario. What’s the worst that can happen for our algorithm?
Consider the following situation
a. A = [ 4, 3, 2, 1 ].
b. A =[ 1, 2, 3, 4 ].
In the first case, the largest value is at the first index position and there-
fore our algorithm uses less operations. However, in the second case, the

4
algorithm uses more operation to find the largest value at the last index po-
sition. In complexity analysis we refer to the first case as Best-case while
the second case, which is more interesting is called the worst-case ; that’s
nothing more than just considering the case when we’re the most unlucky.
So, in the worst case, we have 4 operations to run within the for body, so
finally 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.

3.3 Asymptotic Analysis

In asymptotic analysis, we’ll drop all the terms that grow slowly and only
keep the ones that grow fast as n becomes larger. Clearly 4 remains a 4 as n
grows larger, but 6n grows larger and larger, so it tends to matter more and
more for larger problems. Therefore, the first thing we will do is drop the 4
and keep the function as f( n ) = 6n. The second thing we’ll ignore is the
constant multiplier in front of n, and so our function will become f( n ) =
n. As you can see this simplifies things quite a lot. This filter of ”dropping
all factors” and of ”keeping the largest growing term” as described above is
what we called asymptotic behavior.
Todo:
Find the asymptotic behavior of the following example functions by dropping
the constant factors and by keeping the terms that grow the fastest.

• f( n ) = 8n + 34 gives f( n ) = n.

• f( n ) = 300 gives f( n ) = 1

• f( n ) = n2 + 6n + 42 gives f( n ) = n2

• f( n ) = n3 + 4000n + 1078 gives f( n ) = n3

√
• f( n ) = n + n gives f( n ) = n

• f( n ) =n6 + 3n gives f(n) =n6

• f( n ) = nn + n gives f(n) = nn

Mathematically speaking, what we’re saying here is that we’re interested

in the limit of function f as n tends to infinity; However, in a strict mathe-
matical setting, we would not be able to drop the constants in the limit; but
for computer science purposes, we want to do that for the reasons described
above.

5
Example 2: What is the running time for this code fragment?

Algorithm 2 Running time for nested loop

1: sum = 0;
2: f or(i = 1; i <= n; i + +){
3: f or(j = 1; j <= n; j + +){
4: sum + +;
5: }
6: }

Answer: f(n) =n2

4 Upper Bounds
Several terms are used to describe the running-time equation for an algo-
rithm. These terms — and their associated symbols — indicate precisely
what aspect of the algorithm’s behavior is being described. One is the up-
per bound for the growth of the algorithm’s running time. It indicates the
upper or highest growth rate that the algorithm can have called big-Oh
notation.
Because the phrase “has an upper bound to its growth rate of f(n)” is
long and often used when discussing algorithms, we adopt a special nota-
tion, called big-Oh notation. If the upper bound for an algorithm’s growth
rate (for, say, the worst case) is f(n), then we would write that this algo-
rithm is “in the set O(f(n)) in the worst case” (or just “in O(f(n)) in the
worst case”). For example, if n2 grows as fast as T(n) (the running time
of our algorithm) for the worst-case input, we would say the algorithm is
“in O( n2 ) in the worst case.” The following is a precise definition for an
upper bound. T(n) represents the true running time of the algorithm. f(n)
is some expression for the upper bound.

For T(n) a non-negatively valued function, T(n) is in set O(f(n))

if there exist two positive constants c and n0 such that T(n) ≤ cf(n)
for all n > n0.

Constant n0 is the smallest value of n for which the claim of an upper

bound holds true. Usually n0 is small, such as 1, but does not need to be.
You must also be able to pick some constant c, but it is irrelevant what the

6
value for c actually is. In other words, the definition says that for all inputs
of the type in question (such as the worst case for all inputs of size n) that
are large enough (i.e., n > n0 ), the algorithm always executes in less than
cf(n) steps for some constant c.
Example 1
Consider the sequential search algorithm for finding a specified value in an
array of integers. If visiting and examining one value in the array requires cs
steps where cs is a positive number, and if the value we search for has equal
probability of appearing in any position in the array, then in the average
case T(n) = cs n/2. For all values of n > 1, cs n/2 ≤ cs n. Therefore, by the
definition, T(n) is in O(n) for n0 = 1 and c = cs .
Example 2 Assigning the value from the first position of an array to a
variable takes constant time regardless of the size of the array. Thus, T(n)
= c (for the best, worst, and average cases). We could say in this case that
T(n) is in O(c). However, it is traditional to say that an algorithm whose
running time has a constant upper bound is in O(1)

5 Lower Bound
Similar notation is used to describe the least amount of a resource that an
algorithm needs for some class of input i.e the lower bound of an algorithm.
The lower bound for an algorithm (or a problem, as explained later) is
denoted by the symbol Ω, pronounced “big-Omega” or just “Omega.” The
following definition for is symmetric with the definition of big-Oh.
For T(n) a non-negatively valued function, T(n) is in set (g(n))
if there exist two positive constants c and n0 such that T(n) ≥
cg(n) for all n > n0 .

6 Θ Notation
The definitions for big-Oh and give us ways to describe the upper bound
for an algorithm (if we can find an equation for the maximum cost of a
particular class of inputs of size n) and the lower bound for an algorithm (if
we can find an equation for the minimum cost for a particular class of inputs
of size n). When the upper and lower bounds are the same within a constant
factor, we indicate this by using Θ (big-Theta) notation. An algorithm is
said to be Θ (h(n)) if it is in O(h(n)) and it is in Ω(h(n))
Note that we drop the word “in” for Θ notation, because there is a
strict equality for two equations with the same Θ. In other words, if f(n) is

7
Θ(g(n)), then g(n) is Θ(f(n))
Because the sequential search algorithm is both in O(n) and in Ω (n) in
the average case, we say it is Θ (n) in the average case.
Given an algebraic equation describing the time requirement for an al-
gorithm, the upper and lower bounds always meet. That is because in some
sense we have a perfect analysis for the algorithm, embodied by the running-
time equation. For many algorithms (or their instantiations as programs),
it is easy to come up with the equation that defines their runtime behavior.

6.1 Simplifying Rules

Once you determine the running-time equation for an algorithm, it really is a
simplematter to derive the big-Oh, Ω, and Θ expressions from the equation.
You do not need to resort to the formal definitions of asymptotic analysis.
Instead, you can use the following rules to determine the simplest form.

1. If f(n) is in O(g(n)) and g(n) is in O(h(n)), then f(n) is in O(h(n)).

2. If f(n) is in O(kg(n)) for any constant k > 0, then f(n) is in O(g(n)).

3. If f1(n) is in O(g1(n)) and f2(n) is in O(g2(n)), then f1(n) + f2(n) is

in O(max(g1(n); g2(n))).

4. If f1(n) is in O(g1(n)) and f2(n) is in O(g2(n)), then f1(n)f2(n) is in

O(g1(n)g2(n)).

The first rule says that if some function g(n) is an upper bound for your cost
function, then any upper bound for g(n) is also an upper bound for your
cost function. A similar property holds true for notation: If g(n) is a lower
bound for your cost function, then any lower bound for g(n) is also a lower
bound for your cost function. Likewise for Θ notation.
The significance of rule (2) is that you can ignore any multiplicative
constants in your equations when using big-Oh notation. This rule also
holds true for Ω and Θ notations.
Rule (3) says that given two parts of a program run in sequence (whether
two statements or two sections of code), you need consider only the more
expensive part. This rule applies to Ω and Θ notations as well: For both,
you need consider only the more expensive part.
Rule (4) is used to analyze simple loops in programs. If some action is
repeated some number of times, and each repetition has the same cost, then
the total cost is the cost of the action multiplied by the number of times
that the action takes place. This rule applies to Ω and Θ notations as well.

8
 Taking the first three rules collectively, you can ignore all constants and
all lower-order terms to determine the asymptotic growth rate for any cost
function. The advantages and dangers of ignoring constants were discussed
near the beginning of this section. Ignoring lower-order terms is reason-
able when performing an asymptotic analysis. The higher-order terms soon
swamp the lower-order terms in their contribution to the total cost as n
becomes larger. Thus, if T (n) = 3n4 + 5n2 , then T(n) is in O(n4 ). The n2
term contributes relatively little to the total cost for large n.
Asymptotic comparison operator Numeric comparison opera-
tor
Our algorithm is o( something ) A number is < something
Our algorithm is O( something ) A number is≤ something
Our algorithm is Θ( something ) A number is = something
Our algorithm is Ω( something ) A number is ≥ something
Our algorithm is ω( something ) A number is > something

6.2 Classifying Functions

Given functions f(n) and g(n) whose growth rates are expressed as algebraic
equations, we might like to determine if one grows faster than the other.
The best way to do this is to take the limit of the two functions as n grows
towards infinity,
limx→∞ fg(n)
(n)

If the limit goes to ∞, then f(n) is in Ω (g(n)) because f(n) grows faster.
If the limit goes to zero, then f(n) is in O(g(n)) because g(n) grows faster. If
the limit goes to some constant other than zero, then f(n)= Θ(g(n)) because
both grow at the same rate

6.3 Calculating Running Time

Algorithm 3 Consider a simple for loop

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

The first line is Θ(1). The for loop is repeated n times. The third line
takes constant time so, by simplifying rule (4) of Section 6.1, the total cost

9
for executing the two lines making up the for loop is Θ(n). By rule (3), the
cost of the entire code fragment is also Θ(n).

Algorithm 4 Nested for loop

1: sum = 0;
2: for (j=1; j<=n; j++) // First for loop
3: for (i=1; i<=j; i++) // is a double loop
4: sum++;
5: for (k=0; k<n; k++) // Second for loop
6: 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 Algorithm
4 and takes c2 n = Θ(n) time.
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, by
simplifying rule (4) it has cost c3 i. The outer for loop is executed n times,
but each time the cost of the inner loop is different because it costs c3 i 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 our mathematical preliminaries, we know that
n
X n(n + 1)
i= (1)
2
i=1

which is Θ(n2 ). By simplifying rule (3), Θ (c1 + c2 n + c3 n2 ) is simply

Θ(n2 ).
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
Plogn n times, the total cost
for the first code fragment can be expressed as i=0 n. Note that a variable
substitution takes place here to create the summation, with k = 2i . From
our mathematical preliminaries, the solution for this summation is Θ(n log
n). In the second code fragment, the outer loop is also executed log n + 1

10
Algorithm 5 Not all doubly nested for loops are Θ(n2 ). The following pair
of nested loops illustrates this fact.
1:
sum1 = 0;
for (k=1; k<=n; k*=2) // Do log n times
for (j=1; j<=n; j++) // Do n times
sum1++;
2:
sum2 = 0;
for (k=1; k<=n; k*=2) // Do log n times
for (j=1; j<=k; j++) // Do k times
sum2++;

times. The inner loop

Phas cost k, which doubles each time. The summation
can be expressed as logn
i=0 2 i where n is assumed to be a power of two and

again k = 2i . From Our Mathematical preliminaries, we know that this

summation is simply Θ(n).

7 Complexity Classes
Let’s start by reviewing the definition of A decision problem.

7.1 Decision problem

A Decision problem is a computation problem to which the answer is either
“yes” or “no.” In mathematical language, we can think of a decision prob-
lem as a function whose domain is the set of possible input strings ({0,1}, {
ASCII}, etc.) and whose range is {0,1} (with 0 meaning “no” and 1 meaning
“yes”).

7.2 complexity class

A complexity class is simply a set of decision problems.

11
7.3 Search problems
Search problems—they ask not just whether a solution exists, but also what
the solution is?

7.4 Definition
A complexity class is simply a set of decision problems.

7.5 Problem
Given a graph G and an integer k, is there a spanning tree of size less than k?

For most real-world applications, search problems are much more impor-
tant than decision problems. So why do we restrict our attention to decision
problems when defining complexity classes? Here are a few reasons:

1. The answer to a decision problem is simple.

2. The answer to a decision problem is unique. (A search problem might

have multiple correct answers, e.g., a given graph might have multiple
minimum spanning trees.)

3. A decision problem which asks about the answer to a search problem

is at most as difficult as the search problem itself. For example, if we
can find a minimum spanning tree efficiently, then we can certainly
also solve Problem 1 efficiently

8 Class of P: Polynomial time algorithm

An algorithm is polynomial-time if there exists a constant r such that the
running time on an input of size n is O(nr). The set of all decision problems
which have polynomial-time solutions is called P. Polynomial time is the
shortest class of running times that is invariant across the vast majority
of reasonable, mainstream models of computation. Example of Polynomial
problem: Sorting, Matrix multiplication, Matching

12
8.1 Definition
A decision problem P is in NP if there exists a polynomial-time algorithm
A(x, y) such that, for every input x to the problem P,

P (x) = 1 ⇐⇒ there exists some y such that A(x, y) = 1.

The string y is called a witness or certificate; the algorithm A is called

a verifier or a nondeterministic algorithm. For example, in Problem 1,
the witness y could be the spanning tree itself—we can certainly verify in
polynomial time that a given object y is a spanning tree of size less than k.

8.2 Proposition
P ⊆ NP.

8.3 Proof
. Given a decision problem P, view P as a function whose domain is the set
of strings and whose range is 0,1. If P can be computed in polynomial time,
then we can just take A(x, y)= P(x). In this case, the verifier just re-solves
the entire problem. The converse to the above proposition is a famous open
problem:

8.4 Problem
(P vs. NP). Is it true that P= NP? The vast majority of computer scientists
believe that P 6= NP, and so the P vs. NP problem is sometimes called the
P 6= NP problem. If it were true that P = NP, then lots of problems that
seem hard would actually be easy. The P vs NP relationship is illustrated
on Figure 1

8.5 Hard problems

When we say the problem is “hard” means that the best-known algorithm
for the problem is expensive in its running time. One example of a hard
problem is Towers of Hanoi. It is easy to understand this problem and its
solution. It is also easy to write a program to solve this problem. But, it
takes an extremely long time to run for any “reasonably” large value of n.
Try running a program to solve Towers of Hanoi for only 30 disks!

13
 Figure 1: P Vs NP

The Towers of Hanoi problem takes exponential time, that is, its running
time is Θ(2n ). This is radically different from an algorithm that takes Θ(n
log n) time or Θ(n2 ) time. It is even radically different from a problem
that takes Θ(n4 ) time. These are all examples of polynomial running time,
because the exponents for all terms of these equations are constants.

8.6 Non-deteministic algorithm

An algorithm that works by “guessing” the right answer to a problem—or
checking all possible solutions in parallel to determine which is correct is
called a non-deterministic algorithm, and any problem with an algorithm
that runs on a non-deterministic machine in polynomial time is given a
special name: It is said to be a problem in NP. Thus, problems in NP are
those problems that can be solved in polynomial time on a non-deterministic
machine. However, Not all problems requiring exponential time on a regular
computer are in NP. For example, Towers of Hanoi is not in NP, because
it must print out O(2n ) moves for n disks. A non-deterministic machine
cannot “guess” and print the correct answer in less time.
Moreover, the TRAVELING SALESMAN problem illustrated on Figure
2 is NP-Complete but cannot be solve by non-deterministic algorithms. The
possible way to solve it isby the use of decision problem, which allows to
use YES or NO constructs.

14
Figure 2: An illustration of the TRAVELING SALESMAN problem. Five
vertices are shown, with edges between each pair of cities. The problem is
to visit all of the cities exactly once, returning to the start city, with the
least total cost

8.7 NP-hard
A problem is NP-hard if any problem in NP can be reduce to X in polyno-
mial time. Thus, X is as hard as any problem in NP.

8.8 NP-Complete
These are the problem that we know efficient non-deterministic algorithms
to solve them, but we do not know if there are efficient deterministic algo-
rithms. At the same time, we have not been able to prove that any of these
problems do not have efficient deterministic algorithms. This class of prob-
lems is called NP-complete. What is truly strange and fascinating about
NP-complete problems is that if anybody ever finds the solution to any
one of them that runs in polynomial time on a regular computer, then by a
series of reductions, every other problem that is in NP can also be solved in
polynomial time on a regular computer!
Definition of NP-Complete A problem X is defined to be NP-complete
if

1. X is in NP, and

2. X is NP-hard.

The requirement that a problem be NP-hard might seem to be impossible,

but in fact there are hundreds of such problems, including TRAVELING

15
SALESMAN. Another such problem is called K-CLIQUE. Figure 3 shows
the relationship between P, NP, NP-complete, and exponential time
problems.

Figure 3: Our knowledge regarding the world of problems requiring expo-

nential time or less. Some of these problems are solvable in polynomial
time by a non-deterministic computer. Of these, some are known to be
NP-complete, and some are known to be solvable in polynomial time on a
regular computer.

The primary theoretical advantage of knowing that a problem P1 is

NP-complete is that it can be used to show that another problem P2 is NP-
complete. This is done by finding a polynomial time reduction of P1 to P2.
Because we already know that all problems in NP can be reduced to P1 in
polynomial time (by the definition of NP-complete), we now know that all
problems can be reduced to P2 as well by the simple algorithm of reducing
to P1 and then from there reducing to P2.
There is a practical advantage to knowing that a problem is NP-complete.
It relates to knowing that if a polynomial time solution can be found for any
problem that is NP-complete, then a polynomial solution can be found for
all such problems. The implication is that,

1. Because no one has yet found such a solution, it must be difficult or

impossible to do; and

2. Effort to find a polynomial time solution for one NP-complete problem

can be considered to have been expended for all NP-complete prob-
lems.

16
How is NP-completeness of practical significance for typical programmers?
Well, if your boss demands that you provide a fast algorithm to solve a
problem, he will not be happy if you come back saying that the best you
could do was an exponential time algorithm. But, if you can prove that the
problem is NP-complete, while he still won’t be happy, at least she should
not be mad at you! By showing that her problem is NP-complete, you are
in effect saying that the most brilliant computer scientists for the last 50
years have been trying and failing to find a polynomial time algorithm for
her problem.

References
[1] Clifford A. Shaffer Data Structures and Algorithm Analysis in Java,
Third Edition

17