Computer Science I (University of Central Florida)
Tags: Big-O notation, time complexity, running time, O(1), O(log n), O(n), O(n log n), O(n^2), O(n^3), best case, worst case, average case, summation, closed form, input size
Difficulty: Intermediate | Prerequisites: C Basics, basic algebra
Algorithm analysis answers the question "how does my programme's running time grow as the input gets bigger?" Instead of timing code on a specific machine, you express performance as a mathematical function of the input size, using Big-O notation to capture the upper bound. This section also covers summations, which are the mathematical tool you use to derive those running times from loops. If you can simplify a summation and identify the dominant term, you can analyse nearly any algorithm in the course.
Big-O notation gives an upper bound on how running time scales with input size. The hierarchy from fastest to slowest: O(1), O(log n), O(n), O(n log n), O(n^2), O(n^3). To find the Big-O of an expression, keep only the highest-order term and drop constants. Summation problems on the exam ask you to convert a sigma expression into a closed-form polynomial using standard identities.
Big-O notation (O)
An upper bound on the growth rate of a function. If an algorithm is O(n^2), its running time grows no faster than proportional to n^2 as n increases. Constants and lower-order terms are dropped. In simple terms, Big-O tells you "in the worst case, the time will not grow faster than this."
Running time
The number of operations an algorithm performs, expressed as a function of the input size. Not measured in seconds, because hardware varies.
Input size (n)
The parameter that determines how much work the algorithm has to do. For an array, it is typically the number of elements. For a grid, it might be rows and columns.
Best case
The input scenario where the algorithm performs the fewest operations. For linear search, the best case is finding the target at index 0.
Worst case
The input scenario where the algorithm performs the most operations. For linear search, the worst case is the target not being in the array at all.
Average case
The expected running time averaged over all possible inputs, assuming some probability distribution. Often harder to compute than worst case.
Linear time, O(n)
Running time grows proportionally to the input size. Double the input, roughly double the time.
Logarithmic time, O(log n)
Running time grows proportionally to the logarithm of the input. Common in divide-and-conquer algorithms like binary search.
Summation (sigma notation)
A compact way to express the sum of a sequence. The expression below the sigma gives the starting index, the expression above gives the upper limit, and the body gives the formula for each term.
Closed form
A summation rewritten as a single algebraic expression without the sigma sign. For example, the closed form of the sum of integers from 1 to m is m(m + 1) / 2.
O(1) – constant time (does not depend on input size)
O(log n) – logarithmic time
O(n) – linear time
O(n log n) – linearithmic time (common in efficient sorting: merge sort, quicksort average case)
O(n^2) – quadratic time (nested loops over the input)
O(n^3) – cubic time
The correct ordering from best to worst is: O(1), O(log n), O(n log n), O(n^2). Watch out for distractors that swap O(n) and O(log n), or place O(n log n) before O(n).
Keep the highest-order term; drop everything else
Drop constant multipliers
Examples:
T(n) = 400n^2 + 100 log n - 5 → O(n^2)
n^3 + n → O(n^3)
10^10 * n^3 → O(n^3) (the constant 10^10 is still just a constant)
n^3.2 + n^2 → this is O(n^3.2), which is not O(n^3) because n^3.2 grows faster than n^3
These questions give you a running time formula, a known execution time for one input, and ask you to predict the time for a different input.
Grid algorithm example (Spring 2025 FE):
An algorithm runs in O(R lg C) time on an R × C grid.
Fred: R = 10^6, C = 10^2, time = 3 hours = 10,800 seconds
Shanille: R = 10^2, C = 10^6
Fred's work: 10^6 × 2 lg 10 = 10^6 × 2 × lg 10
Shanille's work: 10^2 × 6 × lg 10
Ratio: (10^2 × 6) / (10^6 × 2) = 6 / (2 × 10^4) = 3 / 10^4
Shanille's time: 10,800 × (3 / 10,000) = 3.24 seconds
Permutation algorithm example (Fall 2024 FE):
An algorithm runs in O(n × n!) time.
n = 9: time = 180 ms, proportional to 9 × 9!
n = 11: proportional to 11 × 11!
Ratio: (11 × 11!) / (9 × 9!) = (11 × 11 × 10 × 9!) / (9 × 9!) = (11^2 × 10) / 9 = 1210 / 9
Time for n = 11: 180 × (1210 / 9) = 180 × 134.44... = 24,200 ms = 24.2 seconds
The method is always the same: compute the ratio of the two running-time expressions, then multiply by the known time.
Key identity: The sum of integers from 1 to m is m(m + 1) / 2.
Worked example (Fall 2024 FE):
Evaluate the summation of (2i + 5) from i = 1 to 3n.
Split: sum of 2i + sum of 5
Sum of 5 from i = 1 to 3n: 5 × 3n = 15n
Sum of 2i from i = 1 to 3n: 2 × sum of i from 1 to 3n = 2 × [3n(3n + 1) / 2] = 3n(3n + 1)
Expand: 3n(3n + 1) = 9n^2 + 3n
Total: 9n^2 + 3n + 15n = 9n^2 + 18n
Steps to follow on any summation problem:
Split the sum into simpler parts (separate additive terms)
Factor constants out of the sigma
Apply the closed-form identity for the sum of integers (or sum of squares, etc.)
Expand and combine like terms
Present in standard polynomial form (not factored)
Sum of first m positive integers:
sum(i, 1 to m) = m(m + 1) / 2
Sum of first m squares:
sum(i^2, 1 to m) = m(m + 1)(2m + 1) / 6
Proportionality method:
time_new = time_known × [f(new input) / f(known input)]
where f is the running-time function.
Algorithm analysis is how engineers choose between competing approaches. If your dataset has 10 million records, the difference between an O(n^2) and an O(n log n) algorithm is the difference between hours and seconds. The proportionality technique shows up in capacity planning: if you know how long your server takes to process today's traffic, you can predict whether it will cope when traffic triples.
Students often think a large constant (like 10^10) in front of n^3 changes the Big-O class. It does not. 10^10 × n^3 is still O(n^3). Big-O drops all constants.
Students confuse "upper bound" with "tight bound." Big-O is an upper bound. Saying an algorithm is O(n^3) does not mean it runs in cubic time; it means cubic time is the ceiling. An O(n) algorithm is also technically O(n^3), but that is not a useful characterisation.
Students sometimes order the complexity classes incorrectly, placing O(n log n) before O(n). O(n) is faster than O(n log n) for large n.
On summation problems, students frequently forget to expand and simplify to standard polynomial form, leaving the answer in factored form when the question asks for the polynomial.
⚠️ Know the correct ordering: O(1), O(log n), O(n), O(n log n), O(n^2), O(n^3). Multiple-choice questions test this directly.
⚠️ Big-O provides an upper bound. This is a fill-in-the-blank or multiple-choice staple.
⚠️ Linear running time = O(n). Tested as a definition question.
⚠️ Be comfortable with proportionality problems. Both the grid (R lg C) and permutation (n × n!) examples are drawn from recent final exams.
⚠️ Summation questions require you to reach standard polynomial form (expanded, not factored).
⚠️ n^3.2 + n^2 is not O(n^3). The exponent 3.2 is greater than 3, so n^3 cannot serve as an upper bound.
True or false: Big-O notation provides a lower bound on running time.
What is the Big-O of T(n) = 400n^2 + 100 log n - 5?
Which is faster for large n: O(n) or O(n log n)?
Fill in the blank: The sum of integers from 1 to m equals ___.
True or false: 10^10 × n^3 is O(n^3).
Answers: 1. False (it is an upper bound) 2. O(n^2) 3. O(n) 4. m(m + 1) / 2 5. True
Q: Which of the following is not O(n^3): n^3 + n, n^3, n^3.2 + n^2, 10^10 × n^3?
A: n^3.2 + n^2. The n^3.2 term grows faster than n^3, so it cannot be bounded above by a constant times n^3.
Q: An algorithm runs in O(R lg C). Fred runs it with R = 10^6, C = 10^2, and it takes 3 hours. Shanille runs it with R = 10^2, C = 10^6. How long does Shanille's run take?
A: 3.24 seconds. The ratio of Shanille's work to Fred's is (10^2 × 6 lg 10) / (10^6 × 2 lg 10) = 3/10,000. Multiply by 10,800 seconds to get 3.24.
Q: Determine the closed form of the summation of (2i + 5) from i = 1 to 3n.
A: 9n^2 + 18n. Split the sum, apply the identity for the sum of the first m integers with m = 3n, expand, and combine.
Q: What do best case, worst case, and average case mean for an algorithm's running time?
A: Best case is the input that causes the fewest operations. Worst case is the input that causes the most. Average case is the expected number of operations across all possible inputs under an assumed probability distribution.
Q: A brute-force algorithm runs in O(n × n!) time. It takes 180 ms for n = 9. How long for n = 11?
A: 24.2 seconds. Compute the ratio 11 × 11! / (9 × 9!) = 11^2 × 10 / 9 ≈ 134.44, multiply by 180 ms, convert to seconds.
Algorithm analysis applies to every data structure and algorithm in the rest of the course: sorting (O(n^2) for bubble/selection sort vs. O(n log n) for merge sort), searching (O(n) for linear vs. O(log n) for binary), and graph algorithms. The summation techniques practised here are the same ones you will use to derive the running time of nested loops and recursive functions.
Big-O notation, time complexity, running time analysis, O(1), O(log n), O(n), O(n log n), O(n^2), O(n^3), upper bound, best case worst case average case, summation closed form, sigma notation, sum of integers formula, proportionality method, algorithm analysis, C 101 UCF, Computer Science I