L02-program Efficiency And Complexity

Lec‐02 Analysis of Algorithms

Umar Manzoor 1

ƒWhat is a “good” or "efficient" program? ƒ How to measure the efficiency of a program? ƒ How to analyse a simple program? ƒ How to compare different programs? ƒ What is the big‐O notation? ƒ What is the impact of input on program performance? ƒ What are the standard program analysis techniques? ƒ Do we need fast machines or fast algorithms?  2

ƒ

An algorithm possesses the following properties: ƒ It must be correct. ƒ It must be composed of a series of concrete steps. ƒ There can be no ambiguity as to which step will be 

performed next. ƒ It must be composed of a finite number of steps. ƒ It must terminate. ƒ ƒ

A computer program is an instance, or concrete  representation, for an algorithm in some  programming language. 3

A solution is said to be efficient if it solves the  problem within its resource constraints. ƒ Space ƒ Time

ƒ

The cost of a solution is the amount of  resources that the solution consumes.

4

The running time of a program.

Program easy to understand? Program easy to code and debug? Program making efficient use of resources? Program running as fast as possible?

5

Ways of measuring efficiency: • Run the program and see how long it takes • Run the program and see how much memory it uses •Problem‐‐‐Lots of variables to control: • What is the input data? • What is the hardware platform?  • What is the programming language/compiler? • Just because one program is faster than another right now,  means it will always be faster?

6

Want to achieve platform‐independence • Use an abstract machine that uses steps of time and  units of memory, instead of seconds or bytes ‐ each elementary operation takes 1 step ‐ each elementary instance occupies 1 unit of memory

7

// Input: int A[N], array of N integers // Output: Sum of all numbers in array A int Sum(int A[], int N) { int s=0; for (int i=0; i< N; i++) s = s + A[i]; return s; } How should we analyse this? 8

1.) Describe the size of the input in terms of one or more parameters: ‐ Input to Sum is an array of N ints, so size is N. 2.) Then, count how many steps are used for an input of      that size: ‐ A step is an elementary operation such as +, <, =, A[i]

9

// Input: int A[N], array of N integers // Output: Sum of all numbers in array A int Sum(int A[], int N { int s=0; 1 for (int i=0; i< N; i++)

2 5

s = s + A[i];

return s; }

6 8

3 7

4 1,2,8: Once 3,4,5,6,7: Once per each iteration of for loop, N iteration Total: 5N + 3 The complexity function of the 10 algorithm is : f(N) = 5N +3

Estimated running time for different values of N: N = 10 N = 100 N = 1,000 N = 1,000,000

=> 53 steps => 503 steps => 5003 steps => 5,000,003 steps

As N grows, the number of steps grow in linear proportion to N for this Sum function. 11

What about the 5 in 5N+3? What about the +3? • As N gets large, the +3 becomes insignificant •5 is inaccurate, as different operations require varying  amounts of time What is fundamental is that the time is linear in N. Asymptotic Complexity: As N gets large, concentrate on the highest order term: • Drop lower order terms such as +3 • Drop the constant coefficient of the highest order term  i.e.  N 12

• The 5N+3 time bound is said to "grow asymptotically"  like N • This gives us an approximation of the complexity of  the algorithm • Ignores lots of (machine dependent) details,  concentrate   on the bigger picture

13

• When n gets large enough, a O(n2)  algorithm  always beats a O(n3)  algorithm. •We shouldn’t ignore  asymptotically  slower algorithms, however. • Real‐world design  situations often  call for a careful balancing of   engineering objectives. • Asymptotic analysis is a useful tool  to help to structure our thinking

What if n0 is very large???

14

Definition: If f(N) and g(N) are two complexity functions,  we say f(N)  = O(g(N)) (read "f(N) as order g(N)", or "f(N) is big‐O of g(N)")

if there are constants c and N0 such that for N >= N0,  f(N) <= c g(N) for all sufficiently large N. 15

Big‐oh notation indicates an upper bound. Example: If T(n) = 3n2 then T(n) is in O(n2). Wish tightest upper bound: While T(n) = 3n2 is in O(n3), we prefer O(n2).

16

ƒ

Worst‐case: (usually) ƒ T(n) = maximum time of algorithm  on any input of size 

n. ƒ

Average‐case: (sometimes) ƒ T(n) = expected time of algorithm  over all inputs of 

size n. ƒ Need assumption of statistical  distribution of inputs. ƒ

Best‐case: (bogus) ƒ Cheat with a slow algorithm that works fast on some 

inputs  17

Not all inputs of a given size take the same time to  run. Example Sequential search for K in an array of n integers: •

Begin at first element in array and look at each  element in turn until K is found

Best case:   Worst case: Average case: 18

Example 1: Finding value X in an array (average  cost). T(n) = csn/2. For all values of n > 1, csn/2 <= csn. Therefore, by the definition, T(n) is in O(n) for n0 = 1 and c = cs.

19

Example 2: T(n) = c1n2 + c2n in average case. c1n2 + c2n <= c1n2 + c2n2 <= (c1 + c2)n2 for all n > 1. T(n) <= cn2 for c = c1 + c2 and n0 = 1. Therefore, T(n) is in O(n2) by the definition. Example 3: T(n) = c.  We say this is in O(1).

20

“The best case for my algorithm is n=1 because  that is the fastest.” WRONG! Big‐oh refers to a growth rate as n grows to ∞. Best case is defined as which input of size n is  cheapest among all inputs of size n.

21

Definition: For T(n) a non‐negatively valued  function, T(n) is in the set Ω(g(n)) if there exist  two positive constants c and n0 such that T(n) >= cg(n) for all n > n0. Meaning: For all data sets big enough (i.e.,  n > n0),  the algorithm always executes in more than  cg(n) steps. Lower bound. 22

T(n) = c1n2 + c2n. c1n2 + c2n >= c1n2 for all n > 1. T(n) >= cn2 for c = c1 and n0 = 1. Therefore, T(n) is in Ω(n2) by the definition. We want the greatest lower bound.

23

ƒ

When big‐Oh and Ω meet, we indicate this  by using Θ (big‐Theta) notation.

ƒ

Definition: An algorithm is said to be  Θ(h(n)) if it is in O(h(n)) and it is in Ω(h(n)).

24

ƒ

Confusing worst case with upper bound.

ƒ

Upper bound refers to a growth rate.

ƒ

Worst case refers to the worst input from  among the choices for possible inputs of  a given size.

25

100n2 Vs 5n3, which one is better?

100 n^2

5 n^3

160000 140000 120000 100000 80000 60000 40000 20000 29

27

25

23

21

19

17

15

13

11

9

7

5

3

1

0

26

100n2 Vs 5n3, which one is better? 100n^2 - 5n^3 10000 0 -10000 -20000

1

3

5 7

9 11 13 15 17 19 21 23 25 27 29 difference

-30000 -40000 -50000

27

As inputs get larger, any algorithm of a smaller order will be more efficient than an algorithm of a larger order

Time (steps)

0.05 N2 = O(N2) 3N = O(N)

N = 60

Input (size) 28

ƒ ƒ

Solve  ½ n2 – 3n = Θ (n2 ) ? Find positive constants c1,c2 and n0  such that c1.n2 ≤ ½ n2 – 3n ≤ c2.n2

29