explain the big oh computation computing for each of the following control structure : sequential , if -then- else , "for" loop ," while" loop
Answers
1. Sequencing:
Suppose our algorithm consists of two parts A and B. A takes time tA and B takes time tB for computation. The total computation "tA + tB" is according to the sequence rule. According to maximum rule, this computation time is (max (tA,tB)).
Example:
Suppose tA =O (n) and tB = θ (n2).
Then, the total computation time can be calculated as
DAA Analyzing Algorithm Control Structure
Computation Time = tA + tB
= (max (tA,tB)
= (max (O (n), θ (n2)) = θ (n2)
. If-then-else:
DAA Analyzing Algorithm Control Structure
The total time computation is according to the condition rule-"if-then-else." According to the maximum rule, this computation time is max (tA,tB).
Example:
Suppose tA = O (n2) and tB = θ (n2)
Calculate the total computation time for the following:
DAA Analyzing Algorithm Control Structure
Total Computation = (max (tA,tB))
= max (O (n2), θ (n2)
The general format of for loop is:
For (initialization; condition; updation)
Statement(s);
Complexity of for loop:
The outer loop executes N times. Every time the outer loop executes, the inner loop executes M times. As a result, the statements in the inner loop execute a total of N * M times. Thus, the total complexity for the two loops is O (N2)
Consider the following loop:
for i ← 1 to n
{
P (i)
}
If the computation time ti for ( PI) various as a function of "i", then the total computation time for the loop is given not by a multiplication but by a sum i.e.
For i ← 1 to n
{
P (i)
}
Takes DAA Analyzing Algorithm Control Structure
If the algorithms consist of nested "for" loops, then the total computation time is
For i ← 1 to n
{
For j ← 1 to n DAA Analyzing Algorithm Control Structure
{
P (ij)
}
}
Example:
Consider the following "for" loop, Calculate the total computation time for the following:
For i ← 2 to n-1
{
For j ← 3 to i
{
Sum ← Sum+A [i] [j]
}
}
Solution:
The total Computation time is:
DAA Analyzing Algorithm Control Structure
4. While loop:
The Simple technique for analyzing the loop is to determine the function of variable involved whose value decreases each time around. Secondly, for terminating the loop, it is necessary that value must be a positive integer. By keeping track of how many times the value of function decreases, one can obtain the number of repetition of the loop. The other approach for analyzing "while" loop is to treat them as recursive algorithms.
Algorithm:
1. [Initialize] Set k: =1, LOC: =1 and MAX: = DATA [1]
2. Repeat steps 3 and 4 while K≤N
3. if MAX<DATA [k],then:
Set LOC: = K and MAX: = DATA [k]
4. Set k: = k+1
[End of step 2 loop]
5. Write: LOC, MAX
6. EXIT
Example:
The running time of algorithm array Max of computing the maximum element in an array of n integer is O (n).
Solution:
array Max (A, n)
1. Current max ← A [0]
2. For i ← 1 to n-1
3. do if current max < A [i]
4. then current max ← A [i]
5. return current max.
The number of primitive operation t (n) executed by this algorithm is at least.
2 + 1 + n +4 (n-1) + 1=5n
2 + 1 + n + 6 (n-1) + 1=7n-2
The best case T(n) =5n occurs when A [0] is the maximum element. The worst case T(n) = 7n-2 occurs when element are sorted in increasing order.
We may, therefore, apply the big-Oh definition with c=7 and n0=1 and conclude the running time of this is O (n).
please mark me as a brianliest
Answer:
Explanation:
In computer , a loop is a programming structure that repeats a sequence of instructions until a specific condition is met. Programmers use loops to cycle through values, add sums of numbers, repeat functions, and many other things. Two of the most common types of loops are the while loop and the for loop. ...