Computer science foundations · 10 minutes
Reasoning about growth
Explain Big O to a beginner using linear and binary search. State the input size, the operation you count and one limitation of the comparison.
Study · reference notes
Relate work to input size
Asymptotic analysis describes how resource use grows with input size. Big O describes an asymptotic upper bound; it is not an exact time in seconds.
Compare growth rates
Worst-case linear search is O(n), while binary search on sorted random-access data is O(log n). Halving the interval leads to logarithmic growth.
State a limitation
Growth rates alone do not specify measured performance on a particular machine or small input. Constants, data representation and setup costs can affect timings.
Independent lesson notes · independent tutor review pending
Sign in to save drafts, receive feedback and schedule reviews. Tutors see only work you submit to their assignments.
Sign in to practice