1 of 30

Lecture 10:

Analysis & Big-O

CS 136: Spring 2024

Katie Keith

2 of 30

Record on Zoom

3 of 30

  • Lab 3: Recursion, released
    • Start early! Use pen and paper!
  • During Labs this week: 1-on-1 feedback /grading for Lab 2
    • Required lab attendance
    • If you are not present (without an excused absence) I will not be able to grade your lab and you will not receive credit.

đź“Ł Announcements

4 of 30

In support of policy goals:

  1. Secure and Expand Scientific Funding,
  2. End Censorship and Political Interference in Science, and
  3. Defend Diversity, Equity, Inclusion, and Accessibility in Science

�Cuts to funding affect YOU: Williams Summer Science student research positions are funded (largely) through federal grants

đź“Ł Announcements

5 of 30

CS 136: Learning Goals

Analysis

Tradeoffs of Time and Space

Advanced Programming

OOP, Java, JUnit, Git

Data Structures*

Use & Implement

​

*Later, we’ll clarify abstract data types versus data structures

6 of 30

  • Big-O notation
  • Calculate Big-O for programs

🎯 Today’s Learning Objectives

7 of 30

đź“šReadings

  • Sedgewick & Wayne. CS:IA. Section 4.1.
  • Sedgewick & Wayne. Algorithms. Section 1.4.

8 of 30

Analysis is almost as old as computer science itself…

Fig credit: Science Museum (London)

9 of 30

Questions you might ask about a program you wrote

  • Why am I waiting so long for my program to run?
  • Why does my program run out of memory?

Today’s focus

10 of 30

To measure the runtime of my program, what’s wrong with looking at the clock to figure out when my program starts and ends (what we call “wall time”)?

đź’ˇThink-pair-share

11 of 30

Answer

đź’ˇThink-pair-share

12 of 30

Example analysis

1. Input:

An array with n elements

2. Approximate

Approximate the program runtime as a function of n. Call this f(n).

3. Describe the order of growth

​

Fig credit

Program runtime

Also could be order of growth of memory use

13 of 30

Intuition for calculating Big-O

  • For some value of n, f(n) is always bounded from above by a constant times another function g(n).
  • Rule of thumb for finding g(n): Look at the largest term and ignore multiplicative constants

So we would say "f(n) is "

Example

14 of 30

Calculate Big-O for the two functions below.

Answer O(n^3)

Answer O(n)

đź’ˇThink-pair-share

15 of 30

Big-O: Formal definition

Let f be a function* and let g be a comparison function*.

We say “f(n) is big-O of g(n)” if there exists constants M>0 and n0 such that

*Both f and g are functions defined on some unbounded subset of the positive real numbers.

absolute value

“for all”

16 of 30

Big-O History

Q: Why do we call it Big-O?

Paul Bachmann, 1837-1920

A: The letter O was chosen by Bachmann to stand for Ordnung, aGerman word meaning (roughly) the order of approximation

17 of 30

How to turn code into a “function”?

We assume the following operations have a constant, unit cost:

​

Operation

Example(s)

Accessing an element of an array

arr[5]

Assigning a value to a variable

int x = 10

Accessing an instance variable

foo.some_data

Elementary mathematical operations

x + 1

y*z

Returning

return x

Incrementing or decrementing

​

i++

j-=1

18 of 30

Be careful with String methods!

public static String mystery(String s){

int strLen = s.length();

​

if(strLen <=1){

return s;

}

​

String a = s.substring(0, strLen/2);

String b = s.substring(strLen/2, strLen);

return mystery(b) + mystery(a);

}

Using .substring() in Java 8 is O(n)

​

It copies each character from the original string to the new substring's character array.

Concatenating two strings in Java 8 is O(n)

​

The + operator creates a new String object and copies the contents of both strings into the new object.

If n is the current number of characters in the input string…

19 of 30

Example: Calculating Big-O from code

c + n*2c

n*2c

  1. public static int linearSearch(int[] array, int target){
  2. int n = array.length;
  3. for (int i = 0; i < n; i++){
  4. if (array[i] == target){
  5. return i;
  6. }
  7. }
  8. return -1;
  9. }

Total & Analysis:

f(n) = 4*nc + 4c

​

g(n) = n

O(n)

c

Here, n is the number of elements in array

Worse case, we never hit this line

int[] theArray = {1, 3, 5, 9, 11};

int index = linearSearch(theArray,10);

Example method call

2c

20 of 30

Examples of order of growth, Part 1

Sedgewick & Wayne. CS:IA. Section 4.1

21 of 30

Examples of order of growth, Part 2

Sedgewick & Wayne. CS:IA. Section 4.1

22 of 30

Running time of algorithms of different orders of growth

Very long = exceeds 10^25 years

Our running example: n is the number of elements in an array

23 of 30

Calculate the big-O time for the program below

// Like the quiz, We assume only n >= 1 given

public static String perfectNumber(int n){

int sum = 1;

for(int i=2; i <= Math.sqrt(n); i++){

if(n%i == 0){

sum += i;

if(i != n/i){

sum += n/i;

}

}

}

if(sum == n){return n + " is a perfect number";}

else{return n + " is not a perfect number";}

}

​

đź’ˇThink-pair-share

24 of 30

More order of growth

n

25 of 30

Binary search algorithm

Binary search locates a target value within a sorted array by

​

  • Repeatedly dividing the search interval in half
  • Comparing the target to the middle element
  • Then narrowing the search to the appropriate half until the target is found or the interval is empty

26 of 30

Search.binarySearch

đź’»

27 of 30

Two search algorithms, different big-O runtimes

Worst case: Target at the end of the array

28 of 30

Proof sketch, Big-O of Binary Search

Board work

29 of 30

Proof sketch, Big-O of Binary Search

30 of 30

  • Big-O notation
  • Calculate Big-O for programs

âś…

âś…

🎯 Today’s Learning Objectives