8- algorithm analysis:- calculate t(n) for recursive function شرح عربي

Main Ideas

The video explains how to form a time recurrence, (T(n)), for a recursive algorithm. It focuses on translating the structure of a recursive function into an equation; solving that equation is presented as a later step.

What Makes a Function Recursive?

A recursive function calls itself from within its own body. A well-formed recursive function has two parts:

• Base case: A condition that stops further calls and returns a result.
• Recursive case: Work that makes one or more calls to the same function, usually with a changed input size.

Without a base case, the function would continue calling itself without stopping.

The factorial function illustrates this: for an input such as 5, it calls itself with 4, then 3, 2, and 1, until it reaches a base case.

How to Write the Recurrence

For a function with input size (n), build (T(n)) by identifying:

1. The non-recursive work in the current call. Count this using the usual techniques for statements and loops. Fixed work is often represented by a constant, such as (1) or (c).
2. The time spent in each recursive call. Identify the input size for each call and include the corresponding (T(\text{new size})) term.
3. The base-case cost. State the time for the stopping input separately, for example, (T(0)=c).

When a function makes multiple recursive calls, include a term for each call. Calls with the same input size can be combined into a coefficient: two calls on inputs of size (n/2) contribute (2T(n/2)).

Examples

• One call with input reduced by 1: If the current call does constant work and then calls itself with (n-1), the recurrence has the form [ T(n)=T(n-1)+c. ]

• One call with input reduced by a fixed amount: A call on (n-4), for example, contributes (T(n-4)), alongside the non-recursive work.

• One call on a halved input: A call on (\lfloor n/2\rfloor) contributes (T(\lfloor n/2\rfloor)), plus the current call’s work.

• Two calls on halved inputs: Two recursive calls on inputs of size (n/2) contribute [ T(n/2)+T(n/2)=2T(n/2), ] in addition to the non-recursive work.

• A recursive call plus a loop: If the current call performs a loop with work proportional to (n), then calls itself on (n-1), the recurrence has the form [ T(n)=T(n-1)+\Theta(n). ]

Important Distinctions

• Non-recursive work can include loops or other statements; it is not necessarily constant.
• The size inside (T(\cdot)) must reflect how the recursive call changes the input.
• A numerical factor in an arithmetic expression does not indicate the number of recursive calls. For example, multiplying a recursive result by 4 is different from making four separate recursive calls.
• The number of recursive calls—not an unrelated constant in the code—determines how many recursive-time terms appear in the recurrence.

After Forming the Recurrence

The resulting (T(n)) is itself a recurrence, not a simple polynomial or other directly analyzed expression. It must first be transformed into a non-recursive form using recurrence-solving methods. Once simplified, familiar asymptotic tools can be used to determine growth rates such as (O), (\Omega), or (\Theta).

Speaker and Source

The material is explained by one instructor or narrator. No other speakers or sources are identifiable in the subtitles.