Change of Variable Method
Duration: 10 min
This video lesson is available to enrolled students.
Inside: a video lesson and guided study material.
Module outline
- Prelims: General Knowledge: Physics Chemistry Biology History Geography Polity Indian Economy Static General Knowledge GK- Current Affairs Environment
- Prelims: General English: Vocabulary Noun Pronoun Adjectives Preposition Articles Direct and Indirect Speech Tenses Conjunction Subject Verb Agreement (Verb Noun Agreement) Modals Sentence Re-arrangements (Para Jumbles) (Narrative Sequencing) Sentence Correction (Error Correction) Sentence Completion (Fill in the blanks) Comprehension / Reading Comprehension / Unseen Passages (Critical Reasoning) (Paragraph Questions) Cloze Test (Cloze Passage) Verbal Analogy (Word Based Analogy) Sentence Construction Adverb Verb
- Prelims: Quantitative Aptitude: Percentage Ratio and Proportion (Ratios) HCF LCM Divisibility Rules Average Sequence and Series (Series) Number System Powers and Exponents (Surds and Indices) Algebra Profit and Loss Simple Interest and Compound Interest Time and Work Pipe and Cistern Speed Time and Distance Mixture and Alligation Mensuration and Geometry Age Problems Partnership Statistics Data Interpretation Arithmetic
- Prelims: General Agriculture: Agriculture in India and Tripura Natural Resource Management Fundamentals of Crop Production Horticulture Crop Improvement Crop Protection Social Science
- IT Mains: Operating System: Introduction to OS Process Management CPU Scheduling Process Synchronization Threads & Process Creation Deadlock Memory Management Virtual Memory Disc Scheduling File Management Distributed Systems
- IT Mains: Computer Networking: Introduction to CN DLL: Access Control DLL: Flow Control DLL: Error Control Data Link Layer - Ethernet Net Layer: IPv4 & Proto Net Layer: IP Addressing Net Layer:Routing Protocol Transport Layer Services TL: Congestion & UDP Application Layer Hardware Basics Network Security
- IT Mains: DBMS: Basics of DBMS ER Diagram Relational Model & Functional Dependencies Keys & Integrity Constraints Normalization (1NF - BCNF) Decomposition Properties & 4NF Relational Algebra SQL Relational Calculus Transaction Management Concurrency Control Database Recovery Big Data Systems Database Security & Authorization Enhanced Data Models NoSQL
- IT Mains: Software Engineering: Fundamentals of Software Engineering Software Requirements and Quality Assurance Software Design, Estimation and Metrics Software Testing Software Maintenance and Configuration Management
- IT Mains: Data Structures & Algorithms: Introduction to DS Array Stack Queue Linked List Tree Graphs Hashing Algorithm Analysis Time Complexity Analysis Sorting Algorithms
- IT Mains: OOPS with C++ & Java: C Fundamentals OOPS with C++ Java Fundamentals Array, String, IO & References OOPS with Java Generic & Collections Multithreading File Handling & I/O
- IT Mains: Python: Introduction to Python Tokens, Variables, Data Types, I/O Operators & Expressions Control Flow & Looping Collections & Strings Functions & Modules
- IT Mains: Website Development: Website, Browser & Services Internet Fundamentals Web Design & Development Protocols & Services Web Publishing & Hosting Server Side & Security Emerging Technologies HTML Basics HTML5 CSS JavaScript-Basics .Net Programming PHP
- IT Mains: Mobile App Development: Mobile Computing Multimedia
- IT Mains: Linux / Windows Server Admin: Unix OS Linux OS
AI summary & chapters
AI Summary
An AI-generated summary of this video lecture.
This lecture introduces the Change of Variable Method, a technique designed to transform non-standard recurrence relations into standard divide-and-conquer forms that satisfy the conditions of the Master Theorem. The instructor begins by defining the standard recurrence form T(n) = aT(n/b) + f(n), explicitly listing the necessary constraints: a >= 1 and b > 1. The core strategy involves substituting a new variable, typically m, to linearize the recursive argument. For recurrences involving roots or fractional exponents like T(n) = aT(n^(1/b)) + f(n), the substitution n = b^m is applied. This transformation converts the recursive term T(n^(1/b)) into a linear form in terms of m, allowing the application of standard asymptotic analysis techniques. The lecture progresses through specific examples, including a recurrence with a k-th root and the classic T(n) = T(sqrt(n)) + 1, demonstrating how to derive a new recurrence S(m), solve it using the Master Theorem cases, and finally substitute back to find the complexity in terms of n.
Chapters
0:00 – 2:00 00:00-02:00
The instructor introduces the Change of Variable Method as a technique to transform non-standard recurrences into standard divide-and-conquer forms suitable for the Master Theorem. He begins writing on the whiteboard, starting to formulate an example or equation related to this method. The instructor writes out the general form of a standard recurrence relation, T(n) = aT(n/b) + f(n), and lists the necessary conditions for its application, specifically noting 'a >= 1' and 'b > 1'. He then begins to define a new variable 'm' as part of the substitution process, setting up the framework for converting complex recursive arguments into linear ones.
2:00 – 5:00 02:00-05:00
The instructor demonstrates the Change of Variable Method to convert a non-standard recurrence relation into a standard divide-and-conquer form suitable for the Master Theorem. He starts with the recurrence T(n) = aT(n^(1/b)) + f(n) and introduces the substitution n = b^m. The process involves substituting this variable into the original equation to simplify the recursive term, showing that T(b^m) = aT(b^(m/b)) + f(b^m). He highlights the simplification of exponents using power rules, where b^(m/b) becomes (b^m)^(1/b), effectively transforming the recursive structure into a standard form T(n) = aT(n/b) + f(n).
5:00 – 9:40 05:00-09:40
The instructor solves a recurrence relation using the Change of Variable Method, specifically addressing T(n) = T(sqrt(n)) + 1. He substitutes variables to transform the original equation into a simpler form, identifying parameters like 'a', 'b', and g(m). He then applies Case 3 of the Master Theorem to derive the final complexity. On-screen text shows the derivation S(m) = aS(m/b) + g(m) where g(m) = 1, leading to the result O(log log n). The instructor highlights specific case conditions and simplifies logarithmic terms, demonstrating the complete workflow from non-standard recurrence to final asymptotic bound.
The lecture systematically builds the Change of Variable Method by first establishing the prerequisites for the Master Theorem, specifically the standard form T(n) = aT(n/b) + f(n). The instructor emphasizes that non-standard recurrences, such as those involving roots like T(n) = aT(n^(1/b)) + f(n), cannot be directly solved without transformation. The key mechanism is the substitution n = b^m, which linearizes the recursive argument. For example, transforming T(n) = aT(n^(1/b)) + f(n) into S(m) = aS(m/b) + g(m). The lecture culminates in solving T(n) = T(sqrt(n)) + 1, where the substitution n = 2^m leads to S(m) = S(m/2) + 1. Applying the Master Theorem yields S(m) = O(log m), which translates back to T(n) = O(log log n). This progression illustrates the method's utility in handling complex recursive structures by reducing them to solvable standard forms.

