Scribd
Upload
51 views6 pages

Algorithm Analysis by Amna Saman

The document discusses algorithm analysis and problem solving strategies. It contains 3 questions: 1) Analyze a sample code and convert it to a recurrence relation using backward substitution. 2) Lists 4 common algorithm strategies: iteration, recursion, brute force, and backtracking. It provides examples and explanations of each. 3) Asks to find the lower, upper, and tight bounds of examples for big O notation.

Uploaded by

Saqib Ameer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
51 views6 pages

Algorithm Analysis by Amna Saman

The document discusses algorithm analysis and problem solving strategies. It contains 3 questions: 1) Analyze a sample code and convert it to a recurrence relation using backward substitution. 2) Lists 4 common algorithm strategies: iteration, recursion, brute force, and backtracking. It provides examples and explanations of each. 3) Asks to find the lower, upper, and tight bounds of examples for big O notation.

Uploaded by

Saqib Ameer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 6

Algorithm Analysis

Submitted By: Amna Saman


Submitted To: Sir Saqib Ameer
Section : BSSE 4th C
Roll No : 14912
Riphah International University of Faisalabad
Assignment NO 1
Q No 1
Consider the following code and just analyze the Code first convert this
code into recurrence realtion then solve the recurrence realtion with the
method of Backward Substitution Method.
Algorithm Test(int n){
If( n > 0)
{
For(I = 0; I < n; I = I * 2){
cout<< I; }
Test(n - 1);
Test(n - 1)
Test(n - 1)} }
Solution

Q No 2
Write Down Any four types of Strategies to solve the Algorithmic
Problems?

Solution

There are many strategies for algorithm design. A quick run-through


of the essential strategies are:
 Iteration

 Recursion

 Brute force

 Backtracking

Iteration

Iteration involves repeating a block of code until a condition is false.


During iteration, the program makes multiple passes through a block of
code.

Iteration can be achieved using loops or recursion (more on this later).


The basic loop constructs are:

 The for loop

 The for-each loop

 The while loop

 The do-while loop

Some functions based on the above loop constructs are


the filter, findAny, and reduce functions.

Recursion
Recursion is repetition achieved through method calls. A recursive
method makes repeated calls to itself before returning a result. A result is
returned if and only if a base case exists.

This base case ensures that the solution converges otherwise an infinite
recursion occurs which in turn leads to a stack overflow.

Recursion is intuitive because each new method call works on clones of


the original problem leading to a final result (if it converges).

Brute Force

This is a naive strategy that considers all possible solutions. This strategy
is also known as the complete or exhaustive search.

By using this approach, if a solution exists, it is guaranteed the solution


will be found. However, the time required to get such a solution might be
impractical. Thus, brute force strategies are generally computationally
expensive even for small inputs.

Backtracking

This strategy solves computational problems by considering only viable


solutions and discarding partial solutions that will prove to be incorrect
later on.
Thus, backtracking adds “intelligence” to the brute force strategy. Why
the need for intelligence? Well, if you know a partial solution leads to a
dead-end (or an eventual incorrect solution), then there is no need going
further with the partial solution. It is simply discarded.

Q NO 3
Find the Lower , Upper And Tight Bound of the following
Examples?

You might also like