This is CS50

• If you didn't get a rubber duck 🦆 last week, ask Yuliia during break or after class!
• Today's snacks, Hello Panda Chocolate Biscuits. 🐼 🍫
• Do say hi or ask questions during break or after class!
• What do today's binary bulbs spell (once sorted)?

n

n/2

n

n/2

n

log₂ n

�

1. Stand up and think of the number 1.

�

• Stand up and think of the number 1.
• Pair off with someone standing, add their number to yours, and remember the sum.

�

• Stand up and think of the number 1.
• Pair off with someone standing, add their number to yours, and remember the sum.
• One of you should then sit down.

�

• Stand up and think of the number 1.
• Pair off with someone standing, add their number to yours, and remember the sum.
• One of you should then sit down.
• If still standing, go back to step 2.

n

n/2

n

n/2

n

log₂ n

searching

input → 

→ output

→ 

→ output

→ bool

→ 

algorithm

linear search

For each door from left to right

If 50 is behind door

Return true

Return false�

For each door from left to right

If 50 is behind door

Return true

Else

Return false

For each door from left to right

If 50 is behind door

Return true

Return false�

For i from 0 to n-1

If 50 is behind doors[i]

Return true

Return false�

binary search

​

​

If 50 is behind middle door

Return true

Else if 50 < middle door

Search left half

Else if 50 > middle door

Search right half

If no doors left

​

If 50 is behind middle door

Return true

Else if 50 < middle door

Search left half

Else if 50 > middle door

Search right half

If no doors left

Return false

If 50 is behind middle door

Return true

Else if 50 < middle door

Search left half

Else if 50 > middle door

Search right half

If no doors left

Return false

If 50 is behind doors[middle]

Return true

Else if 50 < doors[middle]

Search doors[0] through doors[middle - 1]

Else if 50 > doors[middle]

Search doors[middle + 1] through doors[n - 1]

running time

size of problem

time to solve

size of problem

time to solve

O(n)

O(n/2)

O(log₂n)

size of problem

time to solve

O(n)

O(n/2)

O(log₂n)

size of problem

time to solve

O(n)

O(n)

O(log₂n)

size of problem

time to solve

O(n)

O(n)

O(log n)

size of problem

time to solve

O(n)

O(log n)

O

O(n²)

O(n log n)

O(n)

O(log n)

O(1)

O(n²)

O(n log n)

O(n) linear search

O(log n)

O(1)

O(n²)

O(n log n)

O(n) linear search

O(log n) binary search

O(1)

Ω

Ω(n²)

Ω(n log n)

Ω(n)

Ω(log n)

Ω(1)

Ω(n²)

Ω(n log n)

Ω(n)

Ω(log n)

Ω(1) linear search

Ω(n²)

Ω(n log n)

Ω(n)

Ω(log n)

Ω(1) linear search, binary search

Θ

Θ(n²)

Θ(n log n)

Θ(n)

Θ(log n)

Θ(1)

asymptotic notation

linear search

string.h

manual.cs50.io/#string.h

strcmp

data structures

person people[]

​

​

string name;

string number;

​

​

typedef struct

{

string name;

string number;

}

person;

typedef struct

{

string name;

string number;

} person;

​

sorting

input → 

→ output

unsorted → 

→ output

unsorted → 

→ sorted

→ 

→ sorted

7 2 5 4 1 6 0 3

​

→ 

→

7 2 5 4 1 6 0 3

0 1 2 3 4 5 6 7

7 2 5 4 1 6 0 3

selection sort

For i from 0 to n-1

Find smallest number between numbers[i] and numbers[n-1]

Swap smallest number with numbers[i]

7 2 5 4 1 6 0 3

7 2 5 4 1 6 0 3

[i]

7 2 5 4 1 6 0 3

[i]

[i]

[n-1]

7 2 5 4 1 6 0 3

[i]

[i]

[n-1]

7 2 5 4 1 6 0 3

[i]

[i]

[n-1]

7 2 5 4 1 6 0 3

[i]

[i]

[n-1]

7 2 5 4 1 6 0 3

[i]

[i]

[n-1]

7 2 5 4 1 6 0 3

[i]

[i]

[n-1]

0 2 5 4 1 6 7 3

[i]

[i]

[n-1]

0 2 5 4 1 6 7 3

[i]

[i]

[n-1]

0 2 5 4 1 6 7 3

[i]

[i]

[n-1]

0 2 5 4 1 6 7 3

[i]

[n-1]

(n – 1)

​

​

​

​

(n – 1) + (n – 2)

​

​

​

​

(n – 1) + (n – 2) + (n – 3)

​

​

​

​

(n – 1) + (n – 2) + (n – 3) + ... + 1

​

​

​

​

(n – 1) + (n – 2) + (n – 3) + ... + 1

n(n – 1)/2

​

​

​

(n – 1) + (n – 2) + (n – 3) + ... + 1

n(n – 1)/2

(n² – n)/2

​

​

(n – 1) + (n – 2) + (n – 3) + ... + 1

n(n – 1)/2

(n² – n)/2

n²/2 – n/2

​

(n – 1) + (n – 2) + (n – 3) + ... + 1

n(n – 1)/2

(n² – n)/2

n²/2 – n/2

O(n²)

O(n²)

O(n log n)

O(n)

O(log n)

O(1)

O(n²) selection sort

O(n log n)

O(n)

O(log n)

O(1)

For i from 0 to n-1

Find smallest number between numbers[i] and numbers[n-1]

Swap smallest number with numbers[i]

Ω(n²)

Ω(n log n)

Ω(n)

Ω(log n)

Ω(1)

Ω(n²) selection sort

Ω(n log n)

Ω(n)

Ω(log n)

Ω(1)

Θ(n²)

Θ(n log n)

Θ(n)

Θ(log n)

Θ(1)

Θ(n²) selection sort

Θ(n log n)

Θ(n)

Θ(log n)

Θ(1)

bubble sort

Repeat n times

For i from 0 to n-2

If numbers[i] and numbers[i+1] out of order

Swap them

​

​

Repeat n-1 times

For i from 0 to n-2

If numbers[i] and numbers[i+1] out of order

Swap them

​

​

7 2 5 4 1 6 0 3

7 2 5 4 1 6 0 3

[i] [i+1]

2 7 5 4 1 6 0 3

[i] [i+1]

2 7 5 4 1 6 0 3

[i] [i+1]

2 5 7 4 1 6 0 3

[i] [i+1]

2 5 7 4 1 6 0 3

[i] [i+1]

2 5 4 7 1 6 0 3

[i] [i+1]

2 5 4 7 1 6 0 3

[i] [i+1]

2 5 4 1 7 6 0 3

[i] [i+1]

2 5 4 1 7 6 0 3

[i] [i+1]

2 5 4 1 6 7 0 3

[i] [i+1]

2 5 4 1 6 7 0 3

[i] [i+1]

2 5 4 1 6 0 7 3

[i] [i+1]

2 5 4 1 6 0 7 3

[i] [i+1]

2 5 4 1 6 0 3 7

[i] [i+1]

2 5 4 1 6 0 3 7

[i] [i+1]

Repeat n-1 times

For i from 0 to n-2

If numbers[i] and numbers[i+1] out of order

Swap them

​

​

Repeat n-1 times n-1

For i from 0 to n-2

If numbers[i] and numbers[i+1] out of order

Swap them

​

​

Repeat n-1 times n-1

For i from 0 to n-2 n-1

If numbers[i] and numbers[i+1] out of order

Swap them

​

​

Repeat n-1 times n-1

For i from 0 to n-2 n-1

If numbers[i] and numbers[i+1] out of order 1

Swap them

​

​

Repeat n-1 times n-1

For i from 0 to n-2 n-1

If numbers[i] and numbers[i+1] out of order 4

Swap them

​

​

Repeat n-1 times n-1

For i from 0 to n-2 n-1

If numbers[i] and numbers[i+1] out of order

Swap them

​

​

(n – 1) × (n – 1)

​

​

​

​

(n – 1) × (n – 1)

n² – 1n – 1n + 1

​

​

​

(n – 1) × (n – 1)

n² – 1n – 1n + 1

n² – 2n + 1

​

​

(n – 1) × (n – 1)

n² – 1n – 1n + 1

n² – 2n + 1

O(n²)

​

O(n²)

O(n log n)

O(n)

O(log n)

O(1)

O(n²) bubble sort

O(n log n)

O(n)

O(log n)

O(1)

Repeat n-1 times

For i from 0 to n-2

If numbers[i] and numbers[i+1] out of order

Swap them

​

​

Repeat n-1 times

For i from 0 to n-2

If numbers[i] and numbers[i+1] out of order

Swap them

If no swaps

Quit

Ω(n²)

Ω(n log n)

Ω(n)

Ω(log n)

Ω(1)

Ω(n²)

Ω(n log n)

Ω(n) bubble sort

Ω(log n)

Ω(1)

recursion

If no doors left

Return false

If number behind middle door

Return true

Else if number < middle door

Search left half

Else if number > middle door

Search right half

If no doors left

Return false

If number behind middle door

Return true

Else if number < middle door

Search left half

Else if number > middle door

Search right half

1 Pick up phone book

2 Open to middle of phone book

3 Look at page

4 If person is on page

5 Call person

6 Else if person is earlier in book

7 Open to middle of left half of book

8 Go back to line 3

9 Else if person is later in book

10 Open to middle of right half of book

11 Go back to line 3

12 Else

13 Quit

1 Pick up phone book

2 Open to middle of phone book

3 Look at page

4 If person is on page

5 Call person

6 Else if person is earlier in book

7 Open to middle of left half of book

8 Go back to line 3

9 Else if person is later in book

10 Open to middle of right half of book

11 Go back to line 3

12 Else

13 Quit

1 Pick up phone book

2 Open to middle of phone book

3 Look at page

4 If person is on page

5 Call person

6 Else if person is earlier in book

7 Open to middle of left half of book

8 Go back to line 3

9 Else if person is later in book

10 Open to middle of right half of book

11 Go back to line 3

12 Else

13 Quit

1 Pick up phone book

2 Open to middle of phone book

3 Look at page

4 If person is on page

5 Call person

6 Else if person is earlier in book

7 Search left half of book

8

9 Else if person is later in book

10 Search right half of book

11

12 Else

13 Quit

1 Pick up phone book

2 Open to middle of phone book

3 Look at page

4 If person is on page

5 Call person

6 Else if person is earlier in book

7 Search left half of book

8 Else if person is later in book

9 Search right half of book

10 Else

11 Quit

google.com/search?q=recursion

merge sort

​

​

​

Sort left half of numbers

Sort right half of numbers

Merge sorted halves

If only one number

Quit

Else

Sort left half of numbers

Sort right half of numbers

Merge sorted halves

If only one number

Quit

Else

Sort left half of numbers

Sort right half of numbers

Merge sorted halves

1 3 4 6 0 2 5 7

If only one number

Quit

Else

Sort left half of numbers

Sort right half of numbers

Merge sorted halves

6 3 4 1 5 2 7 0

O(n²)

O(n log n)

O(n)

O(log n)

O(1)

log₂ n

log₂ 8

log₂ 2³

3

n log₂ n

n log n

O(n²)

O(n log n) merge sort

O(n)

O(log n)

O(1)

Ω(n²)

Ω(n log n) merge sort

Ω(n)

Ω(log n)

Ω(1)

Θ(n²)

Θ(n log n) merge sort

Θ(n)

Θ(log n)

Θ(1)