CMSC 56 | Lecture 8: Growth of Functions

Growth of Functions
CMSC 56 | Discrete Mathematical Structure for Computer Science
October 6, 2018
Instructor: Allyn Joy D. Calcaben

College of Arts & Sciences
University of the Philippines Visayas

1. Growth of Functions Lecture 8, CMSC 56 Allyn Joy D. Calcaben

2. Big – O Notation

3. Used to measure how well a computer algorithm scales as the amount of data involved increases. Big – O Notation

4. Used to measure how well a computer algorithm scales as the amount of data involved increases. Not a measure of speed but a measure of how well an algorithm scales. Big – O Notation

5. Big – O Notation is also known as Landau Notation Named after Edmund Landau He didn’t invent the notation, he popularized it Ironic that he popularized Big – O as he was known to be an exact and meticulous mathematician Landau Notation

6. If n = 1: 45n 3 + 20n 2 + 19 = Example

7. If n = 1: 45n 3 + 20n 2 + 19 = 84 Example

8. If n = 1: 45n 3 + 20n 2 + 19 = 84 If n = 2: 45n 3 + 20n 2 + 19 = Example

9. If n = 1: 45n 3 + 20n 2 + 19 = 84 If n = 2: 45n 3 + 20n 2 + 19 = 459 Example

10. If n = 1: 45n 3 + 20n 2 + 19 = 84 If n = 2: 45n 3 + 20n 2 + 19 = 459 If n = 10: 45n 3 + 20n 2 + 19 = Example

11. If n = 1: 45n 3 + 20n 2 + 19 = 84 If n = 2: 45n 3 + 20n 2 + 19 = 459 If n = 10: 45n 3 + 20n 2 + 19 = 47, 019 45,000 + 2,000 + 19 Example

12. If n = 100: 45n 3 + 20n 2 + 19 Removing Unimportant Things

13. If n = 100: 45n 3 + 20n 2 + 19 = 45, 000, 000 + 200, 000 + 19 Removing Unimportant Things

14. If n = 100: 45n 3 + 20n 2 + 19 = 45, 000, 000 + 200, 000 + 19 = 45, 200, 019 Removing Unimportant Things

15. If n = 100: 45n 3 + 20n 2 + 19 = 45, 000, 000 + 200, 000 + 19 = 45, 200, 019 = O(N 3 ) Removing Unimportant Things

16. “ Leaving away all the unnecessary things that we don’t care about when comparing algorithms. ” Big – O Notation

17. 2n 2 + 23 vs. 2n 2 + 27 Example

18. 2n 2 + 23 vs. 2n 2 + 27 Essentially they have the same running time. This is another simplification . Solution

19. Definition 1 Given A = f(n), B = g(n) grows faster than f(n), then there exists a number n’ and a constant c so that c•g (n’) ≥ f(n’) for all n’’ > n, we have g(n’’) ≥ f(n’’). Big – O Notation

20. Definition 1 Given A = f(n), B = g(n) grows faster than f(n), then there exists a number n’ and a constant c so that c•g (n’) ≥ f(n’) for all n’’ > n, we have g(n’’) ≥ f(n’’). Since we don’t want to care about constants, we include c so that we can scale g(n). That is, even if we multiply g(n) with a constant c, and it still outgrows f(n), we can still say that g(n) runs at least as fast as f(n). Big – O Notation

21. If the two conditions hold true, we say that f(n) ϵ O(g(n)) f(n) is contained in Big O of g(n) Big O means that g(n) is a function that runs at least as fast as f(n). Big – O Notation

22. f(n) g(n) h(n) n Comparing the Growth Rates

23. Get ¼ and answer. Which of the ff. is true? Write True or False for each number. h(n) ϵ O(f(n)) h(n) ϵ O(g(n)) g(n) ϵ O(f(n)) g(n) ϵ O(h(n)) f(n) ϵ O(g(n)) f(n) ϵ O(h(n)) Comparing the Growth Rates f(n) g(n) h(n) n

24. Get ¼ and answer. Which of the ff. is true? Write True or False for each number. h(n) ϵ O(f(n)) h(n) ϵ O(g(n)) g(n) ϵ O(f(n)) g(n) ϵ O(h(n)) f(n) ϵ O(g(n)) f(n) ϵ O(h(n)) Comparing the Growth Rates f(n) g(n) h(n) n

25. Allow us to concentrate on the fastest growing part of the function and leave out the involved constants Importance

26. Simply about looking at which part of the function grows the fastest. A convenient way of describing the growth of the function while ignoring the distracting and unnecessary details Big – O Notation

27. f(n) = O(g(n)) is also an accepted notation f(n) ϵ O(g(n)) is more accurate, since O(g(n)) is a set of functions. Big – O Notation

28. Algorithm A RT: 3n 2 – n + 10 Algorithm B RT: 2 n – 50n + 256 Which algorithm is preferable in general? Exercise

29. Algorithm A RT: 3n 2 – n + 10 Algorithm B RT: 2 n – 50n + 256 Which algorithm is preferable in general? But, this is for general cases. For small inputs, algorithm B might be equal to algorithm A or better. Solution

30. Algorithm A RT: 3n 2 – n + 10 Algorithm B RT: 2 n – 50n + 256 If n = 5: 3n 2 – n + 10 = 80 2 n – 50n + 256 = 38 If n = 100: 3n 2 – n + 10 = 29910 2 n – 50n + 256 = 1267650600228229401496703200632 Analysis

31. 3n + 1 ϵ _______ 18n 2 – 50 ϵ _______ 9n 4 + 18 ϵ _______ 30n 6 + 2 n + 123 ϵ _______ 2 n n 2 + 30n 6 + 123 ϵ _______ More Example

32. 3n + 1 ϵ O(n) 18n 2 – 50 ϵ O(n 2 ) 9n 4 + 18 ϵ O(n 4 ) 30n 6 + 2 n + 123 ϵ O(2 n ) 2 n n 2 + 30n 6 + 123 ϵ O(2 n n 2 ) More Example

33. O(1) O(log N) O(N) O(N log N) O(N 2 ) O(N 3 ) O(2 n ) Big – O Notation

34. 3n + 1 ϵ O(n 2 ) True / False? More Examples

35. 3n + 1 ϵ O(n 2 ) True. n 2 grows at least as fast as 3n + 1. But this is unusual because we usually try to make the bound as tight as possible. More Examples

36. 3n + 1 ϵ O(n 2 ) True / False? TRUE, but NOT TIGHT More Examples

37. 18n 2 – 50 ϵ O(n 3 ) True / False? If true, tightly bound / not? If not tightly bound, what is the tighter bound? More Examples

38. 18n 2 – 50 ϵ O(n 3 ) True / False? TRUE If true, tightly bound / not? NOT TIGHTLY BOUND If not tightly bound, what is the tighter bound? O(n 2 ) More Examples

39. Write Correct / Incorrect, Tight / Not Tight 4n 2 - 300n + 12 ∈ O(n 2 ) 4n 2 - 300n + 12 ∈ O(n 3 ) 3 n + 5n 2 - 3n ∈ O(n 2 ) 3 n + 5n 2 - 3n ∈ O(4 n ) 3 n + 5n 2 - 3n ∈ O(3 n ) 50•2 n n 2 + 5n - log(n) ∈ O(2 n ) On Your Seats ( 1/4 )

40. Write Correct / Incorrect, Tight / Not Tight 4n 2 - 300n + 12 ∈ O(n 2 ) CORRECT, TIGHT 4n 2 - 300n + 12 ∈ O(n 3 ) CORRECT, NOT TIGHT 3 n + 5n 2 - 3n ∈ O(n 2 ) INCORRECT, NOT TIGHT 3 n + 5n 2 - 3n ∈ O(4 n ) CORRECT, NOT TIGHT 3 n + 5n 2 - 3n ∈ O(3 n ) CORRECT, TIGHT 50•2 n n 2 + 5n - log(n) ∈ O(2 n ) INCORRECT, NOT TIGHT On Your Seats ( 1/4 )

41. O(1) O(log N) O(N) O(N log N) O(N 2 ) O(N 3 ) O(2 n ) Big – O Notation

42. O(1)

43. Constant Description: Statement Example: Adding two numbers c = a + b O(1)

44. Algorithm that will execute at the same amount of time regardless of the amount of data. Or simply, Code that will execute at the same amount of time no matter how big the array is. O(1)

45. Example: Adding element to array list .append ( x ) O(1)

46. O(log N)

47. Logarithmic Description: Divide in Half Data is decreased roughly 50% each time through the algorithm O(log N)

48. Example: Binary Search O(log N)

49. O(N)

50. Linear Description: Loop Time to complete will grow in direct proportion to the amount of data. Example: Factorial of N using Loops for i in range (1, N +1): factorial *= i O(N)

51. Example: Finding the Maximum O(N)

52. Example: Finding the Maximum Look in exactly each item in the array Big difference if it was a 10 – item array vs. a 10 thousand – item array O(N)

53. Example: Linear Search O(N)

54. O(n log N)

55. Linearithmic / Loglinear Description: Divide and Conquer O(n log N)

56. Example: Merge Sort O(n log N)

57. Example: Merge Sort O(n log N)

58. O(N 2 )

59. Quadratic Description: Double Loop Time to complete will grow proportional to the square of amount of data O(N 2 )

60. Example: Bubble Sort O(N 2 )

61. Example: Insertion Sort O(N 2 )

62. O(N 3 )

63. Cubic Description: Triple Loop O(N 3 )

64. O(2 n )

65. Exponential Description: Exhaustive Search (Brute Force*) O(2 n )

66. Implications

67. Given an algorithm that runs in ___ time, the computer can solve a problem size of _____ in a matter of minutes. Practical Implications

68. Given an algorithm that runs in ___ time, the computer can solve a problem size of _____ in a matter of minutes. Constant: any Logarithmic: any Linear: billions Loglinear: hundreds of millions Quadratic: tens of thousands Cubic: thousands Exponential: 30 Practical Implications

69. Best Case, Worst Case

70. count = 0 for each character in string : if character == ‘ a ’: count += 1 Best Case, Worst Case

71. Best case: 2n + 1 Worst case: 3n Running Time

72. We observe the ff. from the algorithm: Each character in the string is considered at most once For each character in the input string, a constant no. of steps is performed (2 or 3) Running Time

73. We observe the ff. from the algorithm: Each character in the string is considered at most once For each character in the input string, a constant no. of steps is performed (2 or 3) With Big – O, we say c 1 n + c 2 ϵ O(n) We say that the running time of the algorithm is O(n) or linear time Running Time