Efficiency: Algorithm Analysis Roughly 'counting the number of operations, assuming all basis operations are of the same unit one
6 Roughly ‘counting’ the number of operations, assuming all basis operations are of the same, unit one. Efficiency: Algorithm Analysis
A Few Simple rules Loops at most the running time of the statements inside the for-loop (including tests ) times the number of iterations O(N) Nested loops for(i=0; i<n; i ++ for (=0; j<n;j ++) k++; the running time of the statement multiplied by the product of the sizes of all the for-loops O(N2)
7 A Few Simple Rules Loops at most the running time of the statements inside the for-loop (including tests) times the number of iterations. O(N) Nested loops the running time of the statement multiplied by the product of the sizes of all the for-loops. O(N2 )
Consecutive statements for(=0;i<n;+) These just add a[i=0; O(N)+O(N2)=O(N2) for (i=0:; k<n:; ++ for (=0; j<n j ++ a+=a]++ Conditional: If s1 else s2 never more than the running time of the test plus the larger of the running times of S1 and S2 O(1)
8 Consecutive statements These just add O(N) + O(N2 ) = O(N2 ) Conditional: If S1 else S2 never more than the running time of the test plus the larger of the running times of S1 and S2. O(1)
Our first example: search of an ordered array Linear search and binary search Upper bound, lower bound and tight bound
9 Our first example: search of an ordered array Linear search and binary search Upper bound, lower bound and tight bound
10 Linear search: // Given an array of 'size, in increasing order, find int linearsearch(int* a[l, int size int x)i int low=0, high=size-li for (int i=0; i<size; i++) O(N) if (a[i]==x return i t
10 O(N) // Given an array of ‘size’ in increasing order, find ‘x’ int linearsearch(int* a[], int size,int x) { int low=0, high=size-1; for (int i=0; i<size;i++) if (a[i]==x) return i; return -1; } Linear search: