<PLACE TITLE HERE>
Presenter Name
Presentation Date
UPHSD – Molino Campus College of Computer Studies
UPHSD – Molino Campus College of Computer Studies
UPHSD – Molino Campus College of Computer Studies
UPHSD – Molino Campus College of Computer Studies
UPHSD – Molino Campus College of Computer Studies
UPHSD – Molino Campus College of Computer Studies
UPHSD – Molino Campus College of Computer Studies
UPHSD – Molino Campus College of Computer Studies
UPHSD – Molino Campus College of Computer Studies
UPHSD – Molino Campus College of Computer Studies
UPHSD – Molino Campus College of Computer Studies
UPHSD – Molino Campus College of Computer Studies
UPHSD – Molino Campus College of Computer Studies
UPHSD – Molino Campus College of Computer Studies
UPHSD – Molino Campus College of Computer Studies
UPHSD – Molino Campus College of Computer Studies
UPHSD – Molino Campus College of Computer Studies
UPHSD – Molino Campus College of Computer Studies
Performance Analysis and Big-O
UPHSD – Molino Campus CS 103 College of Computer Studies
20
Performance Analysis
• Determining an estimate of the time and
memory requirement of the algorithm.
• Time estimation is called time complexity
analysis
• Memory size estimation is called space
complexity analysis.
• Because memory is cheap and abundant, we
rarely do space complexity analysis
• Since time is “expensive” , analysis now
defaults to time complexity analysis
UPHSD – Molino Campus CS 103 College of Computer Studies
21
Big-O Notation
• Let n be a non-negative integer representing
the size of the input to an algorithm
• Let f(n) and g(n) be two positive functions,
representing the number of basic calculations
(operations, instructions) that an algorithm
takes (or the number of memory words an
algorithm needs).
UPHSD – Molino Campus CS 103 College of Computer Studies
22
Big-O Notation (contd.)
• f(n)=O(g(n)) iff there exist a positive constant
C and non-negative integer n0 such that
f(n) Cg(n) for all nn0.
• g(n) is said to be an upper bound of f(n).
UPHSD – Molino Campus CS 103 College of Computer Studies
23
Big-O Notation
(Examples)
• f(n) = 5n+2 = O(n) // g(n) = n
– f(n) 6n, for n 3 (C=6, n0=3)
• f(n)=n/2 –3 = O(n)
– f(n) 0.5 n for n 0 (C=0.5, n0=0)
• n2-n = O(n2) // g(n) = n2
– n2-n n2 for n 0 (C=1, n0=0)
• n(n+1)/2 = O(n2)
– n(n+1)/2 n2 for n 0 (C=1, n0=0)
UPHSD – Molino Campus CS 103 College of Computer Studies
24
Big-O Notation
(In Practice)
• When computing the complexity,
– f(n) is the actual time formula
– g(n) is the simplified version of f
• Since f(n) stands often for time, we use T(n)
instead of f(n)
• In practice, the simplification of T(n) occurs
while it is being computed by the designer
UPHSD – Molino Campus CS 103 College of Computer Studies
25
Simplification Methods
• If T(n) is the sum of a constant number of
terms, drop all the terms except for the most
dominant (biggest) term;
• Drop any multiplicative factor of that term
• What remains is the simplified g(n).
• amnm + am-1nm-1+...+ a1n+ a0=O(nm).
• n2-n+log n = O(n2)
UPHSD – Molino Campus CS 103 College of Computer Studies
26
Big-O Notation
(Common Complexities)
• T(n)=O(1) // constant time
• T(n)=O(log n) // logarithmic
• T(n)=O(n) // linear
• T(n)=O(n2) //quadratic
• T(n)=O(n3) //cubic
• T(n)=O(nc), c 1 // polynomial
• T(n)=O(logc n), c 1 // polylogarithmic
• T(n)=O(nlog n)
UPHSD – Molino Campus CS 103 College of Computer Studies
27
Big-O Notation
(Characteristics)
• The big-O notation is a simplification
mechanism of time/memory estimates.
• It loses precision, trading precision for
simplicity
• Retains enough information to give a ballpark
idea of speed/cost of an algorithm, and to be
able to compare competing algorithms.
UPHSD – Molino Campus CS 103 College of Computer Studies
28
Common Formulas
• 1+2+3+…+n= n(n+1)/2 = O(n2).
• 12+22+32+…+n2= n(n+1)(2n+1)/6 = O(n3)
• 1+x+x2+x3+…+xn=(x n+1 – 1)/(x-1) = O(xn).
UPHSD – Molino Campus CS 103 College of Computer Studies
29
Example of Time Complexity Analysis and Big-O
• Pseudo-code of finding a maximum of x[n]:
double M=x[0];
for i=1 to n-1 do
if (x[i] > M)
M=x[i];
endif
endfor
return M;
UPHSD – Molino Campus CS 103 College of Computer Studies
30
Complexity of the algorithm
• T(n) = a+(n-1)(b+a) = O(n)
• Where “a” is the time of one assignment, and
“b” is the time of one comparison
• Both “a” and “b” are constants that depend
on the hardware
• Observe that the big O spares us from
– Relatively unimportant arithmetic details
– Hardware dependency
UPHSD – Molino Campus CS 103 College of Computer Studies
31
