UNIT SIX

ALGORITHM GROWTH RATES

 ALGORITHM GROWTH RATES

❖ To capture the order of growth of an algorithm’s running time, we

will associate, with each algorithm, a function f(n) that
characterizes the number of primitive operations that are
performed as a function of the input size n.

❖ Often we need to know how running time varies with the

variation of input size.

❖ Behavior of an algorithm for large input is called asymptotic growth.

3/16/2025
 Algorithm growth Rates
• In below example, the running time for MAX algorithm varies as
kN+c
• We can say that running time of MAX algorithm asymptotically varies as
N
• Figure below shows the comparative behavior of two algorithms.
• Observe that for input size less than 5 second algorithm has better
performance.
• On the other hand the second algorithm shows much better
performance for large values of inputs

3/16/2025
 Algorithm Growth Rates

3/16/2025
 Seven functions used in analysis
• It is generally written as Polynomial time algorithms,
• O(1) --- Constant time --- the time does not change in response to the size of the
problem.

• O(n) --- Linear time --- the time grows linearly with the size (n) of the problem.

• O(n2) --- Quadratic time --- the time grows quadratically with the size (n) of the
problem. In big O notation, all polynomials with the same degree are equivalent, so
O(3n2 + 3n + 7) = O(n2)

• Sub-linear time algorithms

• O(logn) -- Logarithmic time

• Super-polynomial time algorithms

• O(n!)

• O(2n)
3/16/2025
 Algorithm growth function

Logarithmic Algorithm

• Running time varies as log N, where N is size of problem.

• It grows slowly, and has the best performance.

• If the problem size increases by factor of 1000, running
time increases by 10

• Example Binary search algorithm

3/16/2025
 Algorithm growth function
Linear Algorithm
• Execution time grows in direct proportion to the size of a
problem.

• Performance is rated as good

• Algorithm, which are based on a single loop, shows linear growth
rate.

• Examples are: searching, deleting and inserting operations in an

array

3/16/2025
 Algorithm Growth Function
N Log N Algorithm
• N log N has high growth rate
• Divide – and – Conquer algorithms show this behavior

Quadratic Algorithm

• Quadratic algorithm grows as the square of the input size

• Problems with two nested loops show quadratic behavior.

• For example, multiplication of two N*N matrices has O(N2) running time.

• Quadratic algorithms have fast growth rates.

3/16/2025
 Algorithm Growth Function
Cubic Algorithm
❖ Running time of a cubic algorithm varies as the cube of the problem size.
❖ Cubic algorithms grow very rapidly.
❖ Problems with three nested loops show cubic behavior
❖ Traversal of a three dimension array has running time O(N3)
Exponential Algorithm
❖ Exponential algorithm has running time of the order of 2N
❖ Growths at high rate, it is not very useful.
❖ Here is a comparison of growth rates of commonly used algorithm
functions
O(log N) < O(N) < O(N log N) < O(N2) < O(N3) < (2N)
3/16/2025
 Comparing Growth Rates

3/16/2025
 Asymptotic Analysis
• Knowing the complexity of algorithms allows you to answer
questions such as

• How long will a program run on an input?

• How much space will it take?

• Is the problem solvable?

• An understanding of algorithmic complexity provides programmers with
insight into the efficiency of their code. Complexity is also important to
several theoretical areas in computer science, including algorithms, data
structures, and complexity theory.
3/16/2025
 Asymptotic analysis

• Asymptotic analysis refers to computing the running time

of any operation in mathematical units of computation. For
example, running time of one operation is computed as f(n)
and may be for another operation it is computed as g(n2).

• Which means first operation running time will increase linearly

with the increase in n and running time of second
operation will increase exponentially when n increases.
Similarly the running time of both operations will be nearly
same if n is significantly small.
 Asymptotic Analysis
• Usually, time required by an algorithm falls under three types −
• Best Case − Minimum time required for program execution.
• Average Case − Average time required for program execution.
• Worst Case − Maximum time required for program execution.
• Asymptotic Notations
• Following are commonly used asymptotic notations used in calculating
running time complexity of an algorithm.
• Ο Notation
• Ω Notation
• θ Notation

3/16/2025
 The “Big-Oh” Notation
T h e Ο(n) is the formal way to express the upper bound of an
algorithm's running time. It measures the worst case time
complexity or longest amount of time an algorithm can possibly
take to complete.
D e f i n i t i o n :Let f (n) and g(n) be functions, where n is a
positive integer. 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) ≤ c·g(n), for n ≥ n0.
T h i s definition is often referred to as the “big-Oh” notation, for it is
sometimes pronounced as
“ f (n) is big-Oh of g(n).”

3/16/2025
 The “Big-Oh” Notation

I l l u s t r a t i n g the “big-Oh” notation. The function f(n)

is O(g(n)), since f(n) ≤ c·g(n) when n ≥ n0.
3/16/2025
 The “Big-Oh” Notation

Examples 1: Show 3n2 + 4n - 2 = O(n2).

We need to find c and n0 such that:
3n2 + 4n - 2 <= cn2 for all n >= n0 .

Divide both sides by n2, getting:

3 + 4/n - 2/n2 <= c for all n >= n0 .

If we choose n0 equal to 1, then we need a value of c such

that:
3 + 4 - 2 <= c

We can set c equal to 6. Now we have:

3n2 + 4n - 2 <= 6n2 for all n >= 1 .
3/16/2025
 The “Big-Oh” Notation
Examples 2: Show n3 != O(n2).

Let's assume to the contrary that

n3 = O(n2).
Then there must exist constants cand n0 such that
n3 != cn2. for all n > = n0.
Dividing by n2, we get:
n < = c for all n > = n0.
But this is not possible; we can never choose a constant c large
enough that n will never exceed it, since n can grow without
bound.
Thus, the original assumption, that n3 = O(n2), must be wrong
so n3 != O(n2).
3/16/2025
 Some Properties of the Big-Oh Notation

 It provides a convenient method for expressing asymptotic

behavior of an algorithm
 When input size becomes large, we simplify Big-Oh representation.
 Any constants in an expression may be ignored.
 O(N2 + 100) = O(N2)
 Lower order terms may be dropped in favor of the highest order term in an
expression
 O(N3 + 2N2 + N) = O(N3)
 The multiplication constants may be ignored.
 O(20N3) = O(N3)

3/16/2025
 Big-Omega Notation, Ω

❖ T h e Ωn is the formal way to express the lower bound of

an algorithm's running time. It measures the best case
time complexity or best amount of time an algorithm
can possibly take to complete.
❖ D e f i n i t i o n : Let f (n) and g(n) be functions mapping positive
integers to positive 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.

❖ T h i s definition allows us to say asymptotically that one
function is greater than or equal to another, up to a
constant factor.
3/16/2025
 Big-Omega Notation, Ω

3/16/2025
 Big-Theta Notation, θ

In addition, there is a notation that allows us to say that two

functions grow at the same rate, up to constant factors.

Definition:

We say that f (n) is θ(g(n)), pronounced “ f (n) is big-Theta of g(n),”

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

c′g(n) ≤ f (n) ≤ c′′g(n), for n ≥ n0.

3/16/2025
 Big-Theta Notation, θ

• The θn is the formal way to express both the lower bound and
upper bound of an algorithm's running time. It is represented
as following

3/16/2025
 In Depth Running Time Analysis
• Generally we perform analysis to find maximum, average and minimum running
times

• Best case Analysis

• Best case analysis is used to determine the minimum running time of algorithm.

• Execution time depends on the nature of input data.

• In Searching problems, for example, the most favorable input is the one which
matches with the very first item in a data collection.

• Likewise, in sorting problems, the best scenario would be when items are
already in sorted order.

• The best case analysis has little practical value.

3/16/2025
 In Depth Running Time Analysis

• Worst Case Analysis

• Worst case analysis determines the running time for most
unfavorable input. It provides maximum running time for a given input.

• In searching, for example, when an item matching with the search key
happens to occur at the end of a data collection.

• Thus worst case analysis yields the most pessimistic time estimate.

• It, however, guarantees that in all circumstances, running time would never exceed
the estimated time.

• In almost all applications, algorithm analysis is done on a worst-case basis.

3/16/2025
 In Depth Running Time Analysis
• Average Case Analysis
• Average case analysis is done to find out the average running time for an
algorithm.

• It lies somewhere between the optimistic and pessimistic times.

• In searching problem, for example the average running time would be
when a data item matching with the search key lies in the middle of a
data collection.

• The average case analysis often relies on probability theory. In most

cases it is difficult to determine average running time of an algorithm.

3/16/2025
 Space Analysis

❖ Space analysis is concerned with determining the maximum

storage requirement needed to implement a particular algorithm.

❖ It provides an estimate of number of bytes as function of input

size

❖ Variables and constants occupy fixed storage, which does not

depend on input size.
Therefore, the space utilization for constants and variables is O(1).
For complex data structures, space utilization is estimated by
counting the number of bytes.

3/16/2025
 Space Analysis

❖ For example, an array of integers of size N, would require 4N bytes.

❖ The space complexity would be O(N)

❖ In some applications, there is trade-off between running time and

storage requirement.

❖ A large data file can be stored more efficiency in shorter time by

using large memory space.
For example, data of two arrays can be merged more efficiently by
using a third array

3/16/2025
 PRACTICE QUESTION (A)

• Algorithms A and B spend exactly TA(n) = 0.1n 2 log10 n

and TB(n) = 2.5n 2 microseconds, respectively, for a
problem of size n. Choose the algorithm, which is better
in the Big-Oh sense, and find out a problem size n0 such
that for any larger size n > n0 the chosen algorithm
outperforms the other. If your problems are of the size n

≤ 109 , which algorithm will you recommend to use?

3/16/2025
 PRACTICE QUESTION (B)

• One of the two software packages, A or B, should be chosen

to process very big databases, containing each up to 1012
records. Average processing time of the package A is TA(n) =
0.1 · n · log2 n microseconds, and the average processing time
of the package B is TB(n) = 5 · n microseconds.

• Which algorithm has better performance in a ”Big-Oh” sense?

Work out exact conditions when these packages outperform
each other.

3/16/2025
 PRACTICE QUESTION (C)

• A sorting method with “Big-Oh” complexity O(n log n)

spends exactly 1 millisecond to sort 1,000 data items.
Assuming that time T(n) of sorting n items is directly
proportional to n log n, that is, T(n) = cn log n, derive a
formula for T(n), given the time T(N) for sorting N items,
and estimate how long this method will sort 1,000,000
items.

3/16/2025
 PRACTICE QUESTION (D)

• A quadratic algorithm with processing time T(n) = cn2

spends T(N) seconds for processing N data items. How
much time will be spent for processing n = 5000 data
items, assuming that N = 100 and T(N) = 1ms?

3/16/2025
 PRACTICE QUESTION (E)

• Software packages A and B of complexity O(n log n) and

O(n), respectively, spend exactly TA(n) = cAn log10 n and
TB(n) = cBn milliseconds to process n data items. During
a test, the average time of processing n = 104 data items
with the package A and B is 100 milliseconds and 500
milliseconds, respectively. Work out exact conditions when
one package actually outperforms the other and
recommend the best choice if up to n = 109 items should
be processed.

3/16/2025
 PRACTICE QUESTION (F)

• Prove that T(n) = a0 + a1n + a2n 2 + a3n 3 is O(n 3 )

using the formal definition of the Big-Oh notation. Hint:
Find a constant c and threshold n0 such that cn3 ≥ T(n)
for n ≥ n0.

3/16/2025
Mwebare | Thank you | Asante