Insider Charity Fraud: Understanding Risks and Controls
This report highlights the prevalence of insider fraud in the charity sector, shedding light on common themes, myths, and research findings. With a focus on the lack of controls as a primary enabling factor, the document delves into the scale of fraud, risk factors, and the necessity for effective oversight in combating fraudulent activities within charities.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Growth of functions CSE 2320 Algorithms and Data Structures Alexandra Stefan Based on presentations by Vassilis Athitsos and Bob Weems University of Texas at Arlington 2/15/2025 1
Math Background Limits From the Limits cheat sheet see: Properties, Basic limit evaluations at (focus on the +), Polynomials at infinity (in Evaluation techniques) L'Hospital's rule on wikipedia (or in the slides below) Derivatives needed to Apply L Hospital s rule From the Derivatives cheat sheet see: Basic Properties and Formulas and Common Derivatives (especially for: polynomial, logarithmic and exponential functions) Logarithm properties See the class cheat sheet Cheat sheets and other useful links are on the Slides and Resources webpage. 2
Book Read chapter 3 Including 3.2 which has useful math review 3
Motivation Be able to understand (read and calculate) Big-Oh notation. E.g. what does this paragraph from wikipedia say? Using big-O notation, the performance of the interpolation algorithm on a data set of size n is O(n); however under the assumption of a uniform distribution of the data on the linear scale used for interpolation, the performance can be shown to be O(log log n).[2][3][4]However, Dynamic Interpolation Search is possible in o(log log n) time using a novel data structure.[5] - https://en.wikipedia.org/wiki/Interpolation_search (Performance section) Is the performance O(n), or O(log log n) or o(log log n) and what do they mean? 4
Asymptotic Bounds Notation Theta is called an asymptotic tight bound Goal: we want to express lower and upper bounds as well. E.g.: Selection sort will take time strictly proportional to n2 (n2 ) Insertion sort will take time at most proportional n2 O(n2 ) Use big-Oh for upper bounding complex functions of n. Note that we can still say that the worst case for insertion sort is (n2 ). Any sorting algorithm will take time at least proportional to n. (n) Math functions that are: (n2 ) : Informal definition: f(n)grows proportional to g(n) if: lim ? (c is a non-zero constant) = . tight bound . O upper bound (big-Oh bigger) . lower bound O(n2 ) : ?(?) ?(?)= c 0 (n2 ) : Abuse notation: ) ( O n f = ( ( )) g n instead of: ) ( n f 5 ( ( )) O g n
Big-Oh A function f(n) is said to be O(g(n)) if there exist constants c0 and n0 such that: f(n) c0g(n) for all n n0. ?(?) ?(?) = c is a constant (0 ok), then ( ) ( ( )). f n O g n Theorem: if lim ? Typically, f(n)is the running time of an algorithm. This can be a rather complicated function. We try to find a g(n) that is simple (e.g. n2), and such that f(n) = O(g(n)). 6
Asymptotic Bounds and Notation (CLRS chapter 3) f(n) is O(g(n)) if there exist positive constants c0 and n0 such that: f(n) c0 g(n) for all n n0. ?(?) ?(?) = 0 or c is a constant, then g(n) is an asymptotic upper bound for f(n). Theorem: if lim ( ) ( ( )) f n O g n ? f(N) is (g(n)) if there exist positive constants c0 and n0 such that: c0g(n) f(n) for all n n0. ?(?) ?(?) = or c , then g(n) is an asymptotic lower bound for f(n). f(n) is (g(n)) if there exist positive constants c0 , c1 and n0 such that: c0 g(n) f(n) c1 g(n) for all n n0. ?(?) ?(?) = c 0 is a constant, g(n) is an asymptotic tight bound for f(n). Theorem: if lim ( ) ( ( )) f n g n ? Theorem: if lim ( ) ( ( )) f n g N ? 7
Asymptotic Bounds and Notation (CLRS chapter 3) little-oh : o ?(?) ?(?) = 0 , then ( ) ( ( )) f n o g n Theorem: if lim ? f(n) is o(g(n)) if for any constant c0, there exists n0 s.t.: f(n) < c0 g(n) for all n n0. g(N) is an asymptotic upper bound for f(N) (but NOT tight). E.g.: n = (n2), n = (nlgn), n2 = (n4), little-omega : ?(?) ?(?) = , then ( ) ( ( )) f n g n Theorem: if lim ? f(N) is (g(n)) if for any constant c0, there exists n0 s. t.: c0 g(n) < f(n) for all n n0. g(n) is an asymptotic lower bound for f(n) (but NOT tight). E.g.: n2 = (n), nlgn = (n), n3 = (n2), 8
LHospitals Rule If lim ? ?(?) and lim and if lim ? ? ?(?) are both 0 or ? (?) is a constant or , ? (?) ?(?) ?(?) = lim ? (?) ? (?) Then lim ? ? 9
Theta vs Big-Oh The Theta notation is more strict than the Big-Oh notation: TRUE: n2 = O(n100). FALSE: n2 = (n100). 10
Properties of O, and 1. f(n) = O(g(n)) => g(n) = (f(n)) 2. f(n) = (g(n)) => g(n) = O(f(n)) 3. f(n) = (g(n)) => g(n) = (f(n)) 4. If f(n) = O(g(n)) and f(n) = (g(n)) => f(n) = (g(n)) 5. If f(n) = (g(n)) => f(n) = O(g(n)) and f(n) = (g(n)) Transitivity (proved in future slides): 6. If ? ? = ? ? ? and ? ? = ?( ? ), then ? ? = ?( ? ). 7. If ? ? = ? ? and ? ? = ( ? ), then ? ? = ( ? ). 11
Simplifying Big-Oh Notation Let f(n) = 35n2 + 41n + lg(n) + 1532. We say that f(n) = O(n2). Also correct, but too detailed (do not use them): f(n) = O(n2+n) f(n) = O(35n2 + 41n + lg(n) + 1532). 12
Asymptotic Notation in Expressions (if needed) In the recurrence formulas and proofs, you may see these notations (see CLRS, page 49): f(n) = 2n2 + (n) There is a function h(n) in (n) s.t. f(n) = 2n2 + h(n) 2n2 + (n) = (n2). For any function h(n) in (n), there is a function g(n) in (n2) s.t. 2n2 + h(n) = g(n). For any function h(n) in (n), 2n2 + h(n) is in (n2). 13
Proofs using the c definition: O Let f(n) = 35n2 + 41n + lg(n) + 1532. Show (using the definition) that f(n) = O(n2). Proof: Want to find n0 and c0 s.t., for all n n0: f(n) c0n2. Version 1: Upper bound each term by n2for large n (e.g. n 1532) f(n) = 35n2 + 41n + lg(n) + 1532 35n2 + n2 + n2 + n2 = 38n2 Use: c0 = 38, n0 = 1536 f(n) = 35n2 + 41n + lg(n) + 1532 38n2, for all n 1536 Version 2: You can also pick c0 large enough to cover the coefficients of all the terms: c0 = 1609 = (35 + 41+1+1532), n0 = 1 14
Proofs using the c definition: , Show (using the definition) that f(n) = (n2) and f(n) = (n2). Let f(n) = 35n2 + 41n + lg(n) + 1532. Want to find n1 and c1 s.t., for all n n1: f(n) c1n2. Use: c1 = 1, n1 = 1 f(n) = 35n2 + 41n + lg(n) + 1532 n2, for all n 1 Proof of : Version 1: We have proved f(n) = O(n2) and f(n) = (n2) and so f(n) = (n2) (property 4, page 26). Proof of : Version 2: We found c0 = 38, n0 = 1536 and c1 = 1, n1 = 1 s.t.: f(n) = 35n2 + 41n + lg(n) + 1532 38n2, for all n 1536 f(n) = 35n2 + 41n + lg(n) + 1532 n2, for all n 1 => n2 f(n) 38n2, for all n 1536 => f(n) = (n2) 15
Polynomial functions If f(n) is a polynomial function, then it is of the dominant term. E.g. f(n) = 15n3 +7n2+3n+20, find g(n) s.t. f(n)= (g(n)): find the dominant term: 15n3 Ignore the constant, left with: n3 => g(n) = n3 => f(n) = (n3) You cannot use the dominant term method if f(n) is a summation that has a number of terms that depends on n. E.g.: f(n) = n2+(n-1) 2+ +22 + 1 See Summations for techniques for solving these. 16
Using Limits ?(?) ?(?) = c is a non-zero constant, then f(n) = ____(g(n)). if lim ? In this definition, both zero and infinity are excluded. In this case we can also say that g(n) = (f(n)). This can easily be proved using the limit or the reflexivity property of . ?(?) ?(?) = c is a constant, then f(n) = _____(g(n)). if lim ? "constant" includes zero, but cannot be infinity. ?(?) ?(?)= then f(n) = _____(g(n)). if lim ? g(n) grows much faster than f(n) ?(?) ?(?) = c is a constant, then f(n) = _____(g(n)). if lim ? "Constant" includes zero, but cannot be infinity. 17
Using Limits ?(?) ?(?) = c is a non-zero constant, then f(n) = (g(n)). if lim ? In this definition, both zero and infinity are excluded. In this case we can also say that g(n) = (f(n)). This can easily be proved using the limit or the reflexivity property of . ?(?) ?(?) = c is a constant, then f(n) = (g(n)). if lim ? "constant" includes zero, but cannot be infinity. ?(?) ?(?)= then f(n) = o(g(n)). if lim ? g(n) grows much faster than f(n) ?(?) ?(?) = c is a constant, then f(n) = O(g(n)). if lim ? "Constant" includes zero, but cannot be infinity. 18
Using Limits: Example 1 Suppose that we are given this running time: f(n) = 35n2 + 41n + lg(n) + 1532. Use the limits theorem to show that f(n) = O(n2). 19
Big-Oh Hierarchy 1 = ?(lg(?)) ??(?) = ?(?) ? = ? ?2 If 0 ? d, then ?? = ?(??). Higher-order polynomials always get larger than lower-order polynomials, eventually. For any ?, if ? > 1, ?? = ? ??. Exponential functions always get larger than polynomial functions, eventually. You can use these facts in your assignments. You can apply transitivity to derive other facts, e.g., that ??(?) = ?(?2). n O(1/n), O(1), ?(??(?)) , ? ? , ? ? ??, ? ?! , ? ?? (where 0< <0.5) () , ? ? , ? ???? , ? ?2, ? ??, 20
n! Compare the following functions (in terms of o, ) nn , n n 2 , ! We can upper and lower bound n! We have a bound on lg(n!): ) lg ( ) ! lg( n n n = Be careful when using lg! Consider: ) ( n n 2 Apply lg = : 2 lg( ) (lg( )) n n 21
Big-Oh Transitivity If ? ? = ? ? ? and ? ? = ?( ? ), then ? ? = ?( ? ). Proof: 22
Big-Oh Transitivity If ? ? = ? ? ? and ? ? = ?( ? ), then ? ? = ?( ? ). Proof: We want to find ?3 and ?3 s.t.? ? ?3 ? ,for all ? ?3. We know: ? ? = ? ? ? => there exist c1, n1, s.t. ? ? ?1? ? ,for all ? ?1 ? ? = ? ? => there exist c2, n2, s.t. g ? ?2 ? ,for all ? ?2 ? ?? ? ?? ? ? ?1? ? ?1?2 ? ,for all ? max(?1,?2) Use: c = c1 * c2 , and ? ???(?1,?2) 23
Using Substitutions If lim ? (?) = , and h(x) is monotonically increasing then: ? ? = ? ? ? ? (?) = ?(? (?) ). (This can be proved ) How do we use that? For example, prove that: ) (lg O n = 10 ( ) n = 2 10 3 ( : (lg ) ( )) for n n O n = ( 10 ) = lg( 2 ( O ) h y n n y Proof: Use substitution: and: (y = h(n)) ) 24
Example Problem 1 Is ? = ?(sin ? ?2)? Answer: 25
Example Problem 2 Show that max(f(n), g(n)) is ?(f(?)+ g(?)) Show O: Show : 26
Asymptotic notation for two parameters (CLRS) f(n,m) is O(g(n,m)) if there exist constants c0, n0 and m0 such that: f(n,m) c0g(n,m) for all pairs (n,m) s.t. either n n0 or m m0 f(n,m) n0 n m0 m 27
Useful logarithm properties ???(?) = ???(?) Proof: apply lg on both sides and you get two equal terms: lg(???(?)) = lg (???(?)) => lg(n) * lg(c) = lg(n) * lg(c) - This equality helps identify false exponentials . E.g. 3??(?) may look like an exponential growth, but is really polynomial: ???(3) . Can we also say that ?? = ?? ? NO! 28
Summary Definitions Properties: transitivity, reflexivity, Using limits Big-Oh hierarchy Substitution Example problems Asymptotic notation for two parameters ?????(?) = ?????(?) exponent) (?? ??)(note logb in the 29
Practice See posted practice problems. 30
Extra: Using Limits: Example 2 Show that ?5+3?4+2?3+?2+?+12 = (???). 5?3+?+3 31
Extra: Using Limits: Example 2 Show that ?5+3?4+?3+2?2+?+12 = (?2). 5?3+?+3 Proof: Here: ? ? =?5+3?4+?3+2?2+?+12 5?3+?+3 Let ?(?) = ?2. ?(?) ?(?)=c 0 and so, ? ? = ? ? . We want to show thatlim ? ?5+3?4+?3+2?2+?+12 5?3+?+3 ?5+3?4+?3+2?2+?+12 ?(?) ?(?)= lim 1 ?2 = lim lim ? 5?5+?3+3?2 ? ? ?5+3?4+?3+2?2+?+12 5?5+?3+3?2 ?(?) ?(?)= lim 1 5 Solution 1: lim = ? ? Solution 2 (L Hospital) : 5?4+3 4?3+3?2+2?+1 5 5?4+3 ?2+3 2? ?(?) ?(?)= lim ? (?) ? (?)= lim 5 4 3 2 ? 5 5 4 3 2 ? = 1 lim ? = = lim 5 ? ? ? 32
