Return to Answer

Yes, this is generally valid. Normally, you can just replace $\lceil n/b \rceil$ with $n/b$ and carry on.

Why is this valid? Let me give three explanations, in order of decreasing amount of hand-waving:

1. Informally, it probably won't make much difference, and probably not enough to change the asymptotics. Asymptotic analysis is about what happens when $n$ gets really big, and when $n$ is really big, there's very little difference between $\lceil n/b \rceil$ and $n/b$ (rounding effects become negligible).

2. Slightly less informally, this is OK when $T(n)$ is a monotonically increasing function of $n$. To justify this, we can start by focusing only on the case where $n$ is a power of $b$, i.e., $n=b^k$. Then the ceilings can be ignored (they do nothing), and the master theorem will apply for sure to $n$ of that form.

So, the standard proof of the master theorem will show that $T(n) \le f(n)$ when $n$ is a power of $b$. What about other values of $n$ that aren't a power of $b$? Well, if $n$ isn't a power of $n$, just round up to the nearest power of $b$: $T(n) \le T(b^k)$ where $k = \lceil \lg_b n \rceil$. Since $f(n)$ grows at most polynomially, it can't grow too fast, and we'll have some constant $c$ such that $f(b^k) \le c \cdot f(b^{k-1})$. Then we know that $T(n)$ is bounded within a narrow range:

$$f(b^{k-1}) \le T(n) \le c \cdot f(b^{k-1}).$$

The upper and lower bounds differ by only a constant factor, so everything gets absorbed into the big-O notation.

3. A more formal justification can be found at Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem.

Yes, this is generally valid. Normally, you can just replace $\lceil n/b \rceil$ with $n/b$ and carry on.

Why is this valid? Let me give three explanations, in order of decreasing amount of hand-waving:

1. Informally, it probably won't make much difference, and probably not enough to change the asymptotics. Asymptotic analysis is about what happens when $n$ gets really big, and when $n$ is really big, there's very little difference between $\lceil n/b \rceil$ and $n/b$ (rounding effects become negligible).

2. Slightly less informally, this is OK when $T(n)$ is a monotonically increasing function of $n$. To justify this, we can start by focusing only on the case where $n$ is a power of $b$, i.e., $n=b^k$. Then the ceilings can be ignored (they do nothing), and the master theorem will apply for sure to $n$ of that form.

So, the standard proof of the master theorem will show that $T(n) \le f(n)$ when $n$ is a power of $b$. What about other values of $n$ that aren't a power of $b$? Well, if $n$ isn't a power of $b$, just round up to the nearest power of $b$: $T(n) \le T(b^k)$ where $k = \lceil \lg_b n \rceil$. Since $f(n)$ grows at most polynomially, it can't grow too fast, and we'll have some constant $c$ such that $f(b^k) \le c \cdot f(b^{k-1})$. Then we know that $T(n)$ is bounded within a narrow range:

$$f(b^{k-1}) \le T(n) \le c \cdot f(b^{k-1}).$$

The upper and lower bounds differ by only a constant factor, so everything gets absorbed into the big-O notation.

3. A more formal justification can be found at Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem.

Yes, this is generally valid. Normally, you can just replace $\lceil n/b \rceil$ with $n/b$ and carry on.

Why is this valid? Let me give three explanations, in order of decreasing amount of hand-waving:

1. Informally, it probably won't make much difference, and probably not enough to change the asymptotics. Asymptotic analysis is about what happens when $n$ gets really big, and when $n$ is really big, there's very little difference between $\lceil n/b \rceil$ and $n/b$ (rounding effects become negligible).

2. Slightly less informally, this is OK when $T(n)$ is a monotonically increasing function of $n$. To justify this, we can start by focusing only on the case where $n$ is a power of $b$, i.e., $n=b^k$. Then the ceilings can be ignored (they do nothing), and the master theorem will apply for sure to $n$ of that form.

So, the standard proof of the master theorem will show that $T(n) \le f(n)$ when $n$ is a power of $b$. What about other values of $n$ that aren't a power of $b$? Well, if $n$ isn't a power of $n$, just round up to the nearest power of $b$: $T(n) \le T(b^k)$ where $k = \lceil \lg_b n \rceil$. Since $f(n)$ grows at most polynomially, it can't grow too fast, and we'll have some constant $c$ such that $f(b^k) \le c \cdot f(b^{k-1})$. Then we know that $T(n)$ is bounded within a narrow range:

$$f(b^{k-1}) \le T(n) \le c \cdot f(b^{k-1}).$$

The upper and lower bounds differ by only a constant factor, so everything gets absorbed into the big-O notation.

3. A more formal justification can be found at Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem.

Yes, this is generally valid. Normally, you can just replace $\lceil n/b \rceil$ with $n/b$ and carry on.

Why is this valid? Let me give three explanations, in order of decreasing amount of hand-waving:

1. Informally, it probably won't make much difference, and probably not enough to change the asymptotics. Asymptotic analysis is about what happens when $n$ gets really big, and when $n$ is really big, there's very little difference between $\lceil n/b \rceil$ and $n/b$ (rounding effects become negligible).

2. Slightly less informally, this is OK when $T(n)$ is a monotonically increasing function of $n$. To justify this, we can start by focusing only on the case where $n$ is a power of $b$, i.e., $n=b^k$. Then the ceilings can be ignored (they do nothing), and the master theorem will apply for sure to $n$ of that form.

So, the standard proof of the master theorem will show that $T(n) \le f(n)$ when $n$ is a power of $b$. What about other values of $n$ that aren't a power of $b$? Well, if $n$ isn't a power of $n$, just round up to the nearest power of $b$: $T(n) \le T(b^k)$ where $k = \lceil \lg_b n \rceil$. Since $f(n)$ grows at most polynomially, it can't grow too fast, and we'll have some constant $c$ such that $f(b^k) \le c \cdot f(b^{k-1})$. Then we know that $T(n)$ is bounded within a narrow range:

$$f(b^{k-1}) \le T(n) \le c \cdot f(b^{k-1}).$$

The upper and lower bounds differ by only a constant factor, so everything gets absorbed into the big-O notation.

3. A more formal justification can be found at Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem.

Yes, this is generally valid. Normally, you can just replace $\lceil n/b \rceil$ with $n/b$ and carry on.

Why is this valid? Let me give three explanations, in order of decreasing amount of hand-waving:

1. Informally, it probably won't make much difference, and probably not enough to change the asymptotics.

2. Slightly less informally, this is OK when $T(n)$ is a monotonically increasing function of $n$. We can focus only on the case where $n$ is a power of $b$, i.e., $n=b^k$. Then the ceilings can be ignored (they do nothing).

The standard proof of the master theorem shows that $T(n) \le f(n)$ when $n$ is a power of $b$. What about other values of $n$ that aren't a power of $b$? Well, if $n$ isn't a power of $n$, just round up to the nearest power of $b$: $T(n) \le T(b^k)$ where $k = \lceil \lg_b n \rceil$. Since $f(n)$ grows at most polynomially, it can't grow too fast, and we'll have some constant $c$ such that $f(b^k) \le c \cdot f(b^{k-1})$. Then we know that $T(n)$ is bounded within a narrow range:

$$f(b^{k-1}) \le T(n) \le c \cdot f(b^{k-1}).$$

The upper and lower bounds differ by only a constant factor, so everything gets absorbed into the big-O notation.

3. A more formal justification can be found at Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem.

Yes, this is generally valid. Normally, you can just replace $\lceil n/b \rceil$ with $n/b$ and carry on.

Why is this valid? Let me give three explanations, in order of decreasing amount of hand-waving:

1. Informally, it probably won't make much difference, and probably not enough to change the asymptotics. Asymptotic analysis is about what happens when $n$ gets really big, and when $n$ is really big, there's very little difference between $\lceil n/b \rceil$ and $n/b$ (rounding effects become negligible).

2. Slightly less informally, this is OK when $T(n)$ is a monotonically increasing function of $n$. To justify this, we can start by focusing only on the case where $n$ is a power of $b$, i.e., $n=b^k$. Then the ceilings can be ignored (they do nothing), and the master theorem will apply for sure to $n$ of that form.

So, the standard proof of the master theorem will show that $T(n) \le f(n)$ when $n$ is a power of $b$. What about other values of $n$ that aren't a power of $b$? Well, if $n$ isn't a power of $n$, just round up to the nearest power of $b$: $T(n) \le T(b^k)$ where $k = \lceil \lg_b n \rceil$. Since $f(n)$ grows at most polynomially, it can't grow too fast, and we'll have some constant $c$ such that $f(b^k) \le c \cdot f(b^{k-1})$. Then we know that $T(n)$ is bounded within a narrow range:

$$f(b^{k-1}) \le T(n) \le c \cdot f(b^{k-1}).$$

The upper and lower bounds differ by only a constant factor, so everything gets absorbed into the big-O notation.

3. A more formal justification can be found at Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem.