Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

General Discussion

Daniel Breen
Daniel Breen
14,943 Points

How Do I Analyze Functions with Master Theorem to Determine Big-O

I've been struggling with understanding Master Theorem for a while now. Most of the info I find seems to assume that I understand certain vocabulary. So here comes a very long question...

Consider the following examples:

const items = [1, 2, 3, 4, 5];

// O(1) Constant Time
const getByIdx = idx => items[idx];
}

// O(n) Linear Time
const findItem = val => {
  for (let i = 0; i < items.length; i++)
    if (items[i] === val) {
      return items[i];
    }
};

// O(n^2) Quadratic Time
const matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

const findItemInMatrix = val => {
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[i].length; j++) {
      if (matrix[i][j] === val) {
        return matrix[i][j]
      }
    }
  }
};

// O(log n) Logarithmic Time
const arr = [1,2,3,4,5,6,7,8,9,10];

const binarySearch = (num, data) => {
  if (data.length === 1) {
    return data[0];
  }

  let low = data.splice(0, Math.ceil(data.length / 2));

  if (num > low[low.length - 1]) {
    return binarySearch(num, data);
  } else {
    return binarySearch(num, low);
  }
}

The examples above are simple enough to determine Big-O without the formula, but I'm curious as to how to use the formula instead:

Master Theorem Formula

According to WIkipedia:

 procedure p( input x of size n ):
   if n < some constant k:
     Solve x directly without recursion
   else:
     Create a subproblems of x, each having size n/b
     Call procedure p recursively on each subproblem
     Combine the results from the subproblems

Here's where I get lost:

What is a subproblem? What lines would be subproblems in my code?
"subproblem" is vague to me. Would a subproblem be...
A statement? return items[i]
An expression? return items[i] + 1
A loop?

What do I plug in for b?
What is b? What piece of code would represent it?

What do I plug in for a?
What is a ? What piece of code would represent it?

What do I plug in for k?
What is k ? What piece of code would represent it?

How would I use the formula on these examples?
Is anyone willing to work through an example using the code samples above in the formula?

Thanks for your help!