Skip to main content
All answers

Computer Science · Sample answer

How do you find the Big-O time complexity of code?

This is a sample explanation showing the kind of help tutors give. It is not an answer from a specific tutor.

The explanation

Big-O describes how the running time of an algorithm grows as the input gets bigger. It ignores the speed of the computer and focuses on the shape of the growth.

Two rules for simplifying:

  • Drop constants: 3n and n/2 are both O(n).
  • Keep only the biggest term: 3n² + 5n + 2 is O(n²), because n² dominates when n is large.

The patterns you will see most:

  • O(1), constant: the work doesn't depend on n. Example: reading the first item of a list.
  • O(n), linear: one loop that visits each of n items once. Example: for each item in the list, add it to a total.
  • O(n²), quadratic: a loop over n inside another loop over n. Example: for each item i, compare it with every item j. That is n × n comparisons.
  • O(log n), logarithmic: the problem is halved on every step. Example: binary search, or a loop that runs while n > 1 and sets n to n / 2.
  • O(n log n): a loop of n steps that each do log n work. Example: merge sort.

Loops in a row add, loops inside each other multiply:

  • A loop over n followed by a separate loop over n: n + n = 2n, which is O(n).
  • A loop over n with a loop over n inside it: n × n, which is O(n²).

A trickier example: for i from 1 to n, for j from i to n, do one step.

  • When i = 1 the inner loop runs n times, when i = 2 it runs n − 1 times, and so on down to 1.
  • Total = n + (n − 1) + … + 1 = n(n + 1) / 2 = ½n² + ½n
  • Dropping constants and smaller terms gives O(n²). Starting the inner loop at i halves the work but doesn't change the growth rate.

How to work it out for any code:

  1. Find what n is (the length of the list, the number given, and so on).
  2. For each loop, ask how many times it runs in terms of n.
  3. Multiply nested loops and add loops in sequence.
  4. Keep the biggest term and drop the constants.

Common mistakes:

  • Calling two separate loops O(n²). They add, so it is O(n).
  • Forgetting hidden loops. Searching a list with a built-in method such as contains or index is itself O(n), so doing that inside a loop gives O(n²).

Up against a deadline? Next time you're stuck on computer science homework and short on time, post it on HomeworkHero with your deadline. There's no posting fee, you compare offers from tutors and choose who to work with, and your payment is held in escrow until you approve the work.

Topics

  • big-o
  • time complexity
  • algorithms
  • computer science

Get help that fits your question.

Post your question with no posting fee, compare offers from tutors who know the subject, and choose who to work with.