Computational Complexity

CSD-202 Data Structure and Algorithms

outline
 Analysis of Algorithms
 Time complexity
 Experimental Analysis
 Big-O Analysis
 Space complexity

2 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Algorithm Analysis
 How one algorithm is more efficient than other to perform same task?
 Like binary search is more efficient than linear search
 Efficiency is all about using resources efficiently and two key resources for a program
are:
1. Running Time:
 How much time it takes to complete
2. Space:
 How much space it occupies while running
 So algorithm analysis is about analyzing:
 Time complexity
 Space complexity

3 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Time Complexity
 Most algorithms transform input into output. The
running time of an algorithm typically grows with the
input size. There can be three different scenarios:
 Worst case
 Maximum number of time an algorithm takes on any input of size
n.
 Best case
 Minimum number of time an algorithm takes on any input of size
n.
 Average case
 Average number of time an algorithm takes on any input of size
n.

4 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Time Complexity
 Worst-case analysis is much easier than average-case analysis, as it requires
only the ability to identify the worst-case input, which is often simple
 So, analysis focus on the worst case running time.
 Easier to analyze
 Crucial to applications such as games, finance and robotics.
 what would happen if an autopilot algorithm ran drastically
slower for some unforeseen, untested inputs
 How to measure running time?
 Experimental Approach
 Measure execution time by implementation and execution
 Growth Rate Or Big-O analysis
 Measure number of steps or statements and determine their growth rate

5 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Experimental Approach
 Implement the algorithm
 Run it on a machine with different input sizes
 Measure the actual running times and plot the results

6 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Experimental Approach
 Problems:
 An algorithm must be fully implemented to study its running time
 Results will vary depending upon hardware of machine, CPU, Memory
 Even same system can take different time for same input, as CPU is shared with other processes.
 Running times of two algorithms are difficult to directly compare unless the
experiments are performed in the same hardware and software environments.
 One program may be better implemented than the other
 Experiments can be done only on a limited set of test inputs; hence, they leave out the
running times of inputs not included in the experiment (and these inputs may be
important).
 A Better Approach?
 Count the steps/statements rather than time

7 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Number of Steps/Statements
 Number of statements executed by an algorithm can be defined as a function T
of n. where n is input size. T(n) is called time complexity function.
 For following algorithm
 Look for elementary operations like:
1. sum= 0
 Variable assignment
2. For i = 1 to n  Math (+, -, *, /, %)
3. sum+= i  Comparisons ( ==, >, <=, ...)
 Calling a method
4. End For
 Returning from a method
5. print sum  Array allocation
 Creating a new object

 T(n)=3n+4
 It means this algorithm will take 3n+4 steps/statements for given value of n.

8 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Example:2
1. sum=0 1 step There can be more then one parameters as
input. In this case T is defined as function of
2. For i=1 to n step 1 i=11 all those parameters.
i<= n n+1 Remember n is input size, it can be anything
3. For j=1 to k step 1 Step 1 increment n like V if we talk about trees, V and E if we
talk about graphs
4. sum=sum+1 j=1n
j<= k n*(k+1)
Step 1 increment n*k
5. End For
1 step (n*k time)
6. End For

7. Print sum 1 step

 T(n,k)=1+1+n+1+n+n+nk+n+nk+nk+1= 3nk+4n+4

9 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Number of Steps/Statements
 Advantages:
 Is performed by studying a high-level description of the algorithm without need for
implementation.
 Allows us to evaluate the relative efficiency of any two algorithms in a way that is
independent of the hardware and software environment.
 Takes into account all possible inputs from best case to worst case.
 Disadvantages:
 Two different algorithm’s time cannot be directly compared

 Solution?
 Focus on growth rate /order of T(n), rather than it’s actual value

10 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Growth Order?
 T(n)=3n+4 T(n)=5n T(n)=n2+100
 Which one is efficient?
 If growth order of one algorithm is slower than other algorithm for very larger
n, we say that algorithm with slower growth order is more efficient than
algorithm with faster growth order.
 This process of approximating growth order of T(n) is called ASYMPTOTIC
COMPLEXITY or ASYMPTOTIC BEHAVIOR of algorithm.

11 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Growth Order?
 How much faster T(n) will grow for larger values of n?
n T(n)=5n2+2n+5 T(n)=3n+3
100 5*10,000+2*100+5 3*100+4
1,000 5*10,00,000+2*1,000+5 3*1,000+4
10,000 5*10,000,000,000+2*10,000+5 3*10,000+4

 As n grows large
 Terms with n changes more than terms which are constant
 constants can be ignored for larger values of n as their contribution to T remains same
 Terms with largest order of n becomes dominant than terms with lower order of n
 It means lower order terms can be neglected for larger values of n to find growth order, because their
contribution to T grows at slower rate with compare to terms with higher order as n grows
 Coefficients can also be neglected
 They become irrelevant when comparing two functions with different order(they shouldn’t be too large
though)

12 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Asymptotic Analysis
 Asymptotic analysis is very useful for comparing algorithm efficiency. It
defines the growth order of algorithm rather than exact number of steps.
 As steps are not universally defined, so T(n) is not very accurate approach to
measure time complexity. Moreover, every machine can take different time for
given steps.
 So Asymptotic analysis categorize the algorithms on basis of their growth
order
 T(n)= 3n+4O(n) T(n)=n2+5n+100O(n2) T(n)= 7n+1000O(n)
 Algorithm with complexity Order n2 is slower than algorithm with Order n
 O stands for Order, and is referred as Big-O

13 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
What is Big-O?
 Let f (n) and g(n) are two functions mapping nonnegative integers to real numbers.
We say that f (n) is O(g(n)) if there exist a real constant c > 0 and an integer constant
n0 ≥ 1 such that:
f (n) ≤ c* g(n), for all n ≥ n0.
 Example: T(n)= 8n-2O(n)
 How?
 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.
c=10
n0=1

 g(n) is called the upper bound or Order of f(n)

 Upper bound means f(n) will not grow faster than g(n) for given c and n0

14 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Big-O
 Example: T(n) = n2 + 3n + 4O(n2)
c=8
n0=1

 Example: T(n)=3log(n)+2 O(log(n)).

c=5
n0=2
Note that log(n) is zero for n = 1. That is why we use n0 = 2.

15 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Big-O Rules
1. If f(n) is a polynomial of degree d, then f(n) is O(nd).
 Drop lower-order terms
 Drop constant factors
 Example: T(n)=5n2+nO(n2)
2. If f(n)=c where c is any constant, then f(n) is O(1)
3. Use the smallest possible class of functions
 Say “2n +3 is O(n)” instead of “O(n2)”
 5n2+n is O(n2) rather than O(n) or O(n3)

16 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Major Growth Orders
 The big-O notation gives an upper bound on the growth rate of a function
 The statement “f(n) is O(g(n))” means that the growth rate of f(n) is no more
than the growth rate of g(n).
 We can use the big-O notation to rank functions according to their growth rate.
 Seven functions are ordered by increasing growth rate in the sequence below, that is, if
a function f (n) precedes a function g(n) in the sequence, then f(n) is O(g(n)):

17 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Growth Rate Comparison
 Growth rate comparison:
Difference is more visible
at larger values of n

18 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Constant
 If input size does not affect the algorithm time
1. int a, b, max; 1. for i=1 to 10 step 1
2. input a 2. print n
3. input b
4. If(a>=b)
5. max=b; INSERT(head,node)
6. else 1. node.next=head
7. max=a; 2. head=node
8. print max

19 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Linear
 When algorithm time is directly proportional to input size
 Single loops 1. for i=0 ; i< n-5; i++)
1. sum=0
2. print i*n
2. for (i=0;i<n;++i)

3. sum++;
1. for (i=1;i<n/2; i+=1)
4. print sum
2. print i*n

20 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Logrithmic
 When algorithm time is proportional to logarithm of input size
 Where loop counter increased with multiplication factor

1. for (i=1;i<=n; i*=2)

2. print i

1. for (i=1;i<=n; i*=3)

2. print i

21 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Logarithm function
 The most common base for the logarithm function in computer science is 2 as computers
store integers in binary. In fact, this base is so common that we will typically omit it from the
notation when it is 2. That is, for us,
 log n = log2 n.
 We note that most handheld calculators have a button marked LOG, but this is typically for
calculating the logarithm base-10, not base-two.
 Computing the logarithm function exactly for any integer n involves the use of calculus, but
we can use an approximation that is good enough for our purposes without calculus. We
recall that the ceiling of a real number, x, is the smallest integer greater than or equal to x,
denoted with ⌈x⌉. The ceiling of x can be viewed as an integer approximation of x since we
have x ≤⌈x⌉ < x+1. For a positive integer, n, we repeatedly divide n by b and stop when
we get a number less than or equal to 1. The number of divisions performed is equal to
⌈logbn⌉. We give below three examples of the computation of ⌈logbn⌉ by repeated divisions:
 • ⌈log327⌉= 3, because ((27/3)/3)/3 = 1;
 • ⌈log464⌉= 3, because ((64/4)/4)/4 = 1;
 • ⌈log212⌉= 4, because (((12/2)/2)/2)/2 = 0.75≤1.

22 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Logarithm Rules
 Given real numbers a > 0, b > 1, c > 0 and d > 1, we have:

23 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Linearithmic/nlogn
 Combination of linear and logarithmic

1. for (i=1;i<=n; i++)

2. for(i=1;i<=n; i*=2)

3. print i

24 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Quadratic
 When algorithm time is directly proportional to square of input size.
 Nested loops
1. sum=0
2. for (i=0;i<n;++i)
3. for (j=0;j<n;++j)
4. sum++ 1. for (i=1;i<n; i++)

5. print sum 2. for (j=1;j<i; j++)

3. print i
 T(n)= 3n2+4n+4
25 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019
Computer Science Department- CIIT Lahore
Cubic
 When algorithm time is directly proportional to cube of input size?
 Triple nested loops
1. sum=0
2. for (i=0;i<n;++i)
3. for (j=0;j<n;++j)
4. for (k=0;k<j;++k)
5. sum++
6. print sum

 T(n)= ??

26 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Exponential
 Involves dynamic programming and brute force algorithms
 Few recursion problems also run in exponential time.
 Exponential Rules: Given positive integers a, b, and c, we have:

27 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Space Complexity
 The number of memory cells which an algorithm needs to complete itself. We will again
focus on worst case and Big-Oh terms.
 Example1 O(1)
1. sum(x, y, z)
2. {
3. set r = x + y + z
4. return r
5. }
 Example2 O(n)
1. sum(a[], n) {
2. r = 0;
3. for (i = 0; i < n; ++i) {
4. r += a[i]
5. }
6. return r
7. }

28 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore
Summary
 In this lecture, we have discussed:
 Complexities of algorithms in terms of time and space
 Time complexity function T(n)
 Asymptotic analysis and Big-O
 Book Chapter4 (Data Structures and Algorithms in Java)

29 Created by Saba Anwar, Revised and edited by Asmara Safdar, 02/09/2019

Computer Science Department- CIIT Lahore