[go: up one dir, main page]
Scribd
Upload
69 views19 pages

Complexity Analysis of Algorithms: Jordi Cortadella Department of Computer Science

This document discusses complexity analysis of algorithms, including estimating runtime, Big O notation, and examples of complexity rankings for different algorithms. It also covers recursion, asymptotic complexity, and how complexity analysis is used to analyze and compare algorithms.

Uploaded by

Atefrachew Seyfu
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
69 views19 pages

Complexity Analysis of Algorithms: Jordi Cortadella Department of Computer Science

This document discusses complexity analysis of algorithms, including estimating runtime, Big O notation, and examples of complexity rankings for different algorithms. It also covers recursion, asymptotic complexity, and how complexity analysis is used to analyze and compare algorithms.

Uploaded by

Atefrachew Seyfu
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/ 19

Complexity Analysis

of Algorithms

Jordi Cortadella
Department of Computer Science
Estimating runtime
What is the runtime of g(n)?
void g(int n) {
for (int i = 0; i < n; ++i) f();
}

void g(int n) {
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) f();
}

Introduction to Programming © Dept. CS, UPC 2


Estimating runtime
What is the runtime of g(n)?

void g(int n) {
for (int i = 0; i < n; ++i)
for (int j = 0; j <= i; ++j) f();
}

Introduction to Programming © Dept. CS, UPC 3


Complexity analysis
• A technique to characterize the execution time of
an algorithm independently from the machine, the
language and the compiler.

• Useful for:
– evaluating the variations of execution time with regard
to the input data
– comparing algorithms

• We are typically interested in the execution time


of large instances of a problem, e.g., when 𝑛 → ∞,
(asymptotic complexity).
Introduction to Programming © Dept. CS, UPC 4
Big O
• A method to characterize the execution time of
an algorithm:
– Adding two square matrices is O(n2)
– Searching in a dictionary is O(log n)
– Sorting a vector is O(n log n)
– Solving Towers of Hanoi is O(2n)
– Multiplying two square matrices is O(n3)
– …

• The O notation only uses the dominating terms


of the execution time. Constants are disregarded.
Introduction to Programming © Dept. CS, UPC 5
Big O: formal definition
• Let T(n) be the execution time of an algorithm when
the size of input data is n.
• T(n) is O(f(n)) if there are positive constants c and n0
such that T(n)  cf(n) when n  n0.
cf(n)

T(n)

n0 n
Introduction to Programming © Dept. CS, UPC 6
Big O: example

• Let T(n) = 3n2 + 100n + 5, then T(n) = O(n2)


• Proof:
– Let c = 4 and n0 = 100.05
– For n  100.05, we have that 4n2  3n2 + 100n + 5

• T(n) is also O(n3), O(n4), etc.


Typically, the smallest complexity is used.

Introduction to Programming © Dept. CS, UPC 7


Big O: examples

Introduction to Programming © Dept. CS, UPC 8


Complexity ranking

Introduction to Programming © Dept. CS, UPC 9


Complexity analysis: examples
Let us assume that f() has complexity O(1)
for (int i = 0; i < n; ++i) f();

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


for (int j = 0; j < n; ++j) f();

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


for (int j = 0; j <= i; ++j) f();

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


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

for (int i = 0; i < m; ++i)


for (int j = 0; j < n; ++j)
for (int k = 0; k < p; ++k) f();
Introduction to Programming © Dept. CS, UPC 10
Complexity analysis: recursion
void f(int n) {
if (n > 0) {
DoSomething(n); // O(n)
f(n/2);
}
}

Introduction to Programming © Dept. CS, UPC 11


Complexity analysis: recursion
void f(int n) { n
if (n > 0) {
DoSomething(n); // O(n) n/2 n/2
f(n/2); f(n/2);
} n/4 n/4 n/4 n/4
}
… … … … … … … …

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Introduction to Programming © Dept. CS, UPC 12


Complexity analysis: recursion
void f(int n) {
if (n > 0) {
DoSomething(n); // O(n)
f(n-1);
}
}

Introduction to Programming © Dept. CS, UPC 13


Complexity analysis: recursion
void f(int n) {
if (n > 0) {
DoSomething(); // O(1)
f(n-1); f(n-1);
}
}

Introduction to Programming © Dept. CS, UPC 14


Asymptotic complexity (small values)

Introduction to Programming © Dept. CS, UPC 15


Asymptotic complexity (larger values)

Introduction to Programming © Dept. CS, UPC 16


Execution time: example
Let us consider that every operation can be
executed in 1 ns (10-9 s).

Introduction to Programming © Dept. CS, UPC 17


How about “big data”?
Source: Jon Kleinberg and Éva Tardos, Algorithm Design, Addison Wesley 2006.

This is often the practical limit for big data

Algorithm Analysis © Dept. CS, UPC 18


Summary
• Complexity analysis is a technique to analyze and compare
algorithms (not programs).

• It helps to have preliminary back-of-the-envelope


estimations of runtime (milliseconds, seconds, minutes,
days, years?).

• Worst-case analysis is sometimes overly pessimistic.


Average case is also interesting (not covered in this course).

• In many application domains (e.g., big data) quadratic


complexity, 𝑂 𝑛2 , is not acceptable.

• Recommendation: avoid last-minute surprises by doing


complexity analysis before writing code.

Introduction to Programming © Dept. CS, UPC 19

You might also like