Scribd
Upload
51 views11 pages

Analysing Complexity of Algorithms

This document discusses analyzing the complexity of algorithms. It covers important resources like time and memory, parameters like problem size and model of computation, and measuring complexity in both concrete and abstract terms. Concrete complexity calculates exact operations while abstract complexity focuses on the dominant term. Complexity is expressed using Big O notation, which describes how functions grow as the problem size increases. The document provides examples of calculating and comparing complexities for different implementations of bubble sort.

Uploaded by

Ngoc
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
51 views11 pages

Analysing Complexity of Algorithms

This document discusses analyzing the complexity of algorithms. It covers important resources like time and memory, parameters like problem size and model of computation, and measuring complexity in both concrete and abstract terms. Concrete complexity calculates exact operations while abstract complexity focuses on the dominant term. Complexity is expressed using Big O notation, which describes how functions grow as the problem size increases. The document provides examples of calculating and comparing complexities for different implementations of bubble sort.

Uploaded by

Ngoc
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 11

Analysing complexity of algorithms

   
Resources and parameters
●
Two important resources:
– Computation time – (how long will it run?)
– Memory – (how much space will it take?)
●
Parameters of measurement
– Problem size
– Model of computation
●
Cases
– Best case, average case, worst case

 
●
Units  

– Time taken (ms, secs etc.), number of operations


Example: Bubble sort
●
Same basic algorithm implemented in 3
different ways:
– goodBubbleSort
– badBubbleSort
– veryBadBubbleSort

   
Concrete Vs Abstract
●
Concrete complexity calculates the exact
number of operations.
●
Abstract complexity is concerned with the
(dominant term of ) the complexity expression
in the worst case.

   
Calculation of complexity
Let n be the size of the array
●
veryBadBubbleSort
n*(n-1)
●
badBubbleSort
(n*(n-1))/2
●
goodBubbleSort
much harder to calculate – depends on the nature of
the actual array. Varies from (n*(n-1))/2 in the worst
case to (n-1) in the best case.
   
Abstract complexity characterizes
the algorithm
●
All three implementations of Bubble sort have
the same abstract complexity.
●
The three implementations differ in concrete
complexity.
●
So abstract complexity is a better measure of
the complexity of the underlying algorithm of an
implementation.

   
How functions vary
Time taken by one operation=1 micro sec.
Problem size N=100
Complexity Time
N 1 micro sec.
N^2 0.01 sec.
N^4 100 sec.
2^N 4x10^16 years

   
Use of dominant term
●
For large problem sizes the dominant term
almost completely determines the value of the
complexity expression.
●
So abstract complexity is expressed in terms of
the dominant term for large N (i.e. large
problem size). Multiplicative constants are also
ignored.

   
Big O notation

f(n) = O(g(n)) means


There are positive constants c and k such that:
0<= f(n) <= c*g(n) for all n >= k.

   
Big O pictorially

   
Example

N^2 + 3n + 4 is O(n^2) since for N>4


N^2 + 3n + 4 is O(n^2) < 2N^2
that is c=2 and k=4.

   

You might also like