COMP2121 Chap.3 Big-O Notation and Sets
Big-O Notation and Sets
Comparing growth
Big-O notation states that one function eventually grows no faster than a constant multiple of another. A proof names a constant c and a threshold N and checks the inequality for every n from N on.
Omega gives the matching lower bound and Theta requires both, which is how running times are compared.
Sets and their algebra
Sets are collections in which order and repetition do not matter.
The chapter covers membership, the empty set, cardinality, subsets, the power set with its two to the n subsets, and the operations of union, intersection, difference and complement with their identities.
Writing a Big-O proof the course accepts
A complete answer names a constant c and a threshold N, then shows the inequality for every n from N onwards.
The standard technique bounds each lower-order term by a multiple of the leading power, which is valid once n is at least one. A disproof assumes constants exist and derives a contradiction, usually by dividing through and letting n grow past c.
Logarithms to different bases differ by a constant factor, so the base does not matter inside Big-O.
Sets in proofs and counting
Set identities mirror the logic laws: union matches or, intersection matches and, and complement matches not, so De Morgan's laws for sets follow from those for propositions.
A proof of equality usually takes an arbitrary element of one side and follows it through the definitions to the other side, then repeats the argument in reverse. The power set of a set with n elements has two to the n members, which reappears in counting as the number of subsets of a finite set.
What this chapter covers
- 01
Big-O definition with witnesses
- 02
Omega and Theta
- 03
Sets and membership
- 04
Subsets and equality
- 05
Power sets
- 06
Set operations and identities
Worked example · free
Compare growth rates with witnesses
- 2Bound each term of 3n plus 5 by a multiple of n.
- 1Name the constants c and N.
- 2Refute the second claim from the definition.
Key terms
- Big-O notation
- A statement that a function is eventually bounded above by a constant multiple of another.
- Power set
- The collection whose members are exactly the subsets of a given set.
- Cardinality
- The number of elements in a finite set.
Big-O Notation and Sets FAQ
What do the constants c and N do?
The constant c absorbs fixed factors such as a faster machine, and the threshold N lets you ignore small inputs where the slower-growing function happens to be larger. Any valid pair proves the bound.
Is the empty set the same as the set containing it?
No. The empty set has no elements, while the set whose only element is the empty set has one element. The distinction matters in cardinality and power set questions.
How do I prove two sets are equal?
Show each is a subset of the other. Start each direction with an arbitrary element and follow it through the definitions, or rewrite with set identities that mirror the logic laws.
Does the base of a logarithm matter in Big-O?
No. A logarithm to one base is a constant multiple of a logarithm to any other base, so log base 2 of n and log base 10 of n belong to the same Big-O class, and the base is usually left out.
What is the difference between a subset and an element?
An element is a member of a set, while a subset is a set all of whose members belong to the other set. The number 1 is an element of the set containing 1 and 2, and the set containing only 1 is a subset of it. Mixing the two symbols is a frequent slip.
Exam move
Practise one Big-O proof that bounds each lower-order term by the leading power, and one disproof that derives a contradiction from assumed constants. For sets, draw a Venn diagram to guess an identity, then prove it by double inclusion. List the power set of a small set by hand to fix the two to the n count. Add one set-membership proof each day, written out for an arbitrary element in both directions.
Keep a ranked list of common growth rates, from logarithmic through polynomial to exponential, and place each new function on it.
Working through Big-O Notation and Sets in COMP2121? Sia is AskSia’s AI Computer Science tutor — ask any COMP2121 Big-O Notation and Sets question and get a clear, step-by-step explanation grounded in how COMP2121 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.