CODEWITHSUNDEEP
algorithmperformancetimebig-ocomplexity-theory
n828
n828

Reputation: 39

One problem to cover all the time complexities

A college instructor here. I am trying to find a meaningful (practical) code example to illustrate different time complexities for beginners in a ELi5 manner. The code should start with constant complexity and then incrementally, by adding small piece of code, increases in complexity: .., logn, n, nlogn, n^2, 2^n, ..

I think I can explain it better with one example that has small incremental changes rather than switch the context from searching to sorting to brute force algorithms .

Upvotes: 2

Views: 61

Answers (1)

btilly
btilly

Reputation: 46487

Any example will be artificial. But here is one that does reasonably well.

Let vec be a sorted array of numbers, i an integer, and x be another number. In order answer the following questions.

  1. O(1) What is the value of vec[i]?
  2. O(n) Is x in a range from vec by linear search?
  3. O(log(n)) Is x in a range from vec by binary search?
  4. O(n^2) Is x the sum of two elements in a range from of vec by a double loop?
  5. O(n log(n)) Is x the sum of two elements of vec by linear search on the first with a binary search on the second. (Simplifying trick, do a linear search on the smaller and binary on the second. then reuse your code from 3.)
  6. O(2^n) Is x the sum of any subset of elements of vec by recursion?
  7. (pseudopolynomial) Memoize the previous solution. Discuss memory vs speed tradeoffs.

Upvotes: 2

Related Questions