CS 161 Section - W1: Asymptotic Analysis, Proof by Induction - Spring 2023

Oct 14, 2026

Upload by Kurz

Lecture section notes for CS 161 covering W1 topics: asymptotic analysis and proof by induction, with emphasis on how to reason about algorithm performance. Includes pseudocode guidance for designing a clear step-by-step procedure (e.g., matching a socket to a light bulb) and examples illustrating acceptable versus lecture-derived algorithm descriptions. Provides Big-O notation definitions using English, picture/intuitive runtime growth concepts, and formal mathematical conditions, plus structured advice for formally proving Big-O bounds by choosing constants c and n0.

LanguageEnglish

CategoryPresentations

FormatPDF

Pages38

Reading Time13 min

AccessFree to download

W1: Asymptotic analysis, proof by induction

Pseudocode guidelines and examples

BIG-O notation

Proving BIG-O bounds

CS 161 Section W1: Asymptotic analysis, proof by induction. Spring 2023 Modiﬁed by Sophia Sanchez from Avery Wang’s Winter 2021 ACE Section PSEUDOCODE What is good pseudocode? 2 PSEUDOCODE Clear description of the steps Setup: You have light bulbs of different sizes placed in order of their size, and have 1 socket. How do you match the sock to the light bulb? | find_matching_light_bulb (LightBulbs, Socket)
search the light bulbs and return the matching lightbulb with the socket | find_matching_light_bulb (lightBulbs, socket)
for lightBulb in lightBulbs:
if lightBulb and socket match: return lightBulb
return no matching light bulb found | | --- | --- | PSEUDOCODE Use algorithms covered in lectures without their pseudocode | find_matching_light_bulb (LightBulbs, Socket)
run binary_search to find the matching light bulb. | find_matching_light_bulb (lightBulbs, socket)
ind= modified_binary_search(lightBulbs,
socket)
if lightBulbs[ind] matches with socket:
return lightBulbs[ind] else:
return no matching light bulb found
❖ modified_binary_search is binary_search, but we change it [in this specific way]. | | --- | --- | PSEUDOCODE Simplify pseudocode as much as possible | find_matching_light_bulb (lightBulbs, socket) if the 1st light bulb matches the socket:
return the first light bulb
if the 2nd light bulb matches the socket: return the 2nd light bulb
if the 3rd light bulb matches the socket: return the 3rd light bulb
…
if the nth light bulb matches the socket:
return the nth light bulb return no matching light bulb found | find_matching_light_bulb (lightBulbs, socket)
for lightBulb in lightBulbs:
if lightBulb and socket match: return lightBulb
return no matching light bulb found | | --- | --- | PSEUDOCODE Clear description of the steps Use algorithms covered in lectures without their pseudocode Simplify pseudocode as much as possible BIG-O NOTATION 7 BIG-O NOTATION Let T(n) & f(n) be functions deﬁned on the positive integers. (In this class, we’ll typically write T(n) to denote the worst case runtime of an algorithm) What do we mean when we say “T(n) is O(f(n))”? In English T(n) = O(f(n)) if and only if T(n) is eventually upper bounded by a constant multiple of f(n) In Pictures Runt ime (ms) n 0 n (input size) c ·f(n) T(n) f(n) In Math T(n) = O(f(n)) if and only if there exists positive constantsc and n0 such that for all n ≥ n0 T(n) ≤ c · f(n) 8 BIG-O NOTATION Let T(n) & f(n) be functions deﬁned on the positive integers. (In this class, we’ll typically write T(n) to denote the worst case runtime of an algorithm) What do we mean when we say “T(n) is O(f(n))”? In English T(n) = O(f(n)) if and only if T(n) is eventually upper bounded by a constant multiple of f(n) In Pictures Runt ime (ms) n 0 n (input size) c ·f(n) T(n) f(n) In Math T(n) = O(f(n)) “for all” “if and only if” ⇔ ∃ c , n0 > 0 s.t. ∀ n ≥ n0 , T(n) ≤ c · f(n) “such that” “there exists” 9 PROVING BIG-O BOUNDS If you’re ever asked to formally prove that T(n) is O(f(n)), use the MATH deﬁnition: T(n) = O(f(n)) ⇔ ∃ c , n0 > 0 s.t. ∀ n ≥ n0 , must be constants! T(n) ≤ c · f(n) i. . ce&penn0dcannon n!ot ● To prove T(n) = O(f(n)), you need to announce your c & n0 up front! ○ Play around with the expressions to ﬁnd appropriate choices of c & n0 (positive constants) ○ Then you can write the proof! Here how to structure the start of the proof: “Let c = and n0 = . We will show that T(n) ≤ c ・f(n) for all n ≥ n0 .”

FAQs

What does it mean to say T(n) is O(f(n))?

T(n) = O(f(n)) means T(n) is eventually bounded above by a constant multiple of f(n). The formal statement uses the existence of positive constants c and n0 such that for all n ≥ n0, T(n) ≤ c · f(n).

How should pseudocode be written in this section?

Pseudocode should provide a clear description of the steps. The notes contrast an explicit step description with variants that reuse lecture algorithms (e.g., binary search) while simplifying pseudocode as much as possible and maintaining readable logic.

How do you formally prove that T(n) is O(f(n))?

Use the mathematical definition: announce c and n0 up front, then show that T(n) ≤ c · f(n) for all n ≥ n0. The proof must ensure those chosen values are positive constants.

Oct 14, 2026

Upload by Kurz