How to Solve T(n) = T(n-1) + log n

TL;DR

The recurrence expands into a sum of logarithms, giving T(n) = 1 + log 1 + log 2 + ... + log n. Combining the logarithms produces 1 + log(n!), and bounding the factorial by n^n gives 1 + log(n^n) = 1 + n log n. Therefore, the asymptotic order is O(n log n).

Transcript

Dear students, welcome to Gate Smashers In this video I am going to solve recurrence relation And I will solve this recurrence relation with back substitution method Guys I have already told you that whenever we start algorithm Or which we call DA, whenever we start DA algorithm So the first topic comes that is your recurrence one And I have alrea... Read More

Key Insights

• Back substitution is a method for solving the recurrence by repeatedly expanding smaller inputs. For T(n) = T(n-1) + log n, each substitution reduces the argument of T by one and adds another logarithmic term to the expression.
• Consistent substitution is essential because every occurrence of n must change together. When deriving T(n-1), the recursive term becomes T(n-2), while log n becomes log(n-1), giving T(n-1) = T(n-2) + log(n-1).
• Repeated expansion creates a recognizable sequence. The first substitutions produce T(n-2) + log(n-1) + log n, followed by T(n-3) + log(n-2) + log(n-1) + log n.
• The general expansion contains T(n-k) and a consecutive collection of logarithmic terms. Setting the recursive argument to the termination input reduces T(n-k) to T(1), whose stated value is 1.
• The accumulated logarithms run from log 1 through log n after termination. This sequence represents every logarithmic contribution introduced while the recurrence decreases its input one step at a time.
• The logarithm addition rule converts a sum into the logarithm of a product. Therefore, log 1 + log 2 + log 3 + ... + log n becomes log(1 × 2 × 3 × ... × n).
• The product of the integers from 1 through n is n factorial. Consequently, the recurrence can be expressed as T(n) = 1 + log(n!) after the recursive substitutions reach the stated base condition.
• The factorial is bounded in the derivation by n^n because its factors are treated as no greater than n. Thus, 1 + log(n!) is bounded by 1 + log(n^n), which simplifies to 1 + n log n and O(n log n).

Questions & Answers

Q: How do you solve T(n) = T(n-1) + log n by substitution?

Start by writing T(n-1) = T(n-2) + log(n-1), then substitute that expression into the original recurrence. Repeating the process generates T(n-3), T(n-4), and further reduced terms while accumulating consecutive logarithms. When the recursive argument reaches 1, use T(1) = 1. The resulting logarithmic sum becomes log(n!), which is bounded using n^n to obtain O(n log n).

Q: What pattern appears when the recurrence is expanded repeatedly?

The expansion reduces the recursive argument by one during every substitution and adds the logarithm associated with that stage. Early expressions include T(n-2) + log(n-1) + log n and T(n-3) + log(n-2) + log(n-1) + log n. Continuing this pattern eventually leaves the base term T(1) together with the consecutive sum log 1 + log 2 + ... + log n.

Q: Why must every occurrence of n be replaced during substitution?

Every occurrence of n belongs to the same recurrence input, so replacing n with n-1 affects both parts of the formula. The term T(n-1) becomes T(n-2), and log n becomes log(n-1). Forgetting to change the logarithmic term would break the consecutive sequence needed for the later sum and would prevent the expansion from matching the recurrence described in the lesson.

Q: How does the termination condition end the expansion?

The stated termination condition is T(1) = 1. After expressing the repeated substitution with a reduced argument such as T(n-k), the process chooses the substitution count that makes that argument equal to 1. The recursive portion can then be replaced by its known value, leaving 1 plus all logarithmic contributions accumulated while the argument decreased from n toward the base input.

Q: Why does the sum of logarithms become log(n!)?

After termination, the accumulated terms are log 1 + log 2 + log 3 + ... + log n. The logarithm rule presented in the lesson says that adding logarithms corresponds to taking the logarithm of their product. The sum therefore becomes log(1 × 2 × 3 × ... × n). Since that product is the factorial sequence, it is written as log(n!).

Q: How is n factorial bounded in the recurrence solution?

The derivation writes n! as a product containing n, n-1, n-2, and the remaining decreasing factors. For the stated worst-case bound, each factor is treated as being no greater than n, and there can be up to n such factors. The product is therefore bounded by n multiplied by itself n times, which is n^n.

Q: How does log(n^n) simplify to n log n?

Once the factorial expression is bounded by n^n, the recurrence is written in the form 1 + log(n^n). The logarithm rule used in the derivation moves the exponent n in front of the logarithm, changing log(n^n) into n log n. The remaining constant 1 does not change the stated asymptotic result, so the final order is O(n log n).

Q: Why is back substitution used for this recurrence relation?

Back substitution exposes how the recurrence changes at each smaller input. It calculates terms such as T(n-1) and T(n-2), substitutes them into earlier expressions, and reveals the sequence of logarithms that must be combined. The lesson presents this approach as broadly useful, including for recurrence relations where the master theorem fails, and emphasizes practicing the individual algebraic steps carefully.

Summary & Key Takeaways

• Back substitution begins by calculating T(n-1), T(n-2), and later terms from the original recurrence. Replacing n consistently in both the recursive term and logarithmic term reveals a pattern containing T(n-k) followed by logarithms of consecutive values. This pattern makes the full expansion easier to identify and terminate.

• The termination condition T(1) = 1 ends the recursive expansion. After applying it, the accumulated terms become log 1 + log 2 + log 3 + ... + log n. The logarithm addition rule combines this sequence into the logarithm of the product 1 × 2 × 3 × ... × n.

• The product 1 × 2 × 3 × ... × n is written as n!, so the expanded recurrence becomes 1 + log(n!). The derivation bounds n! by n multiplied by itself n times, producing n^n. Applying the logarithm rule then gives 1 + n log n and O(n log n).