3) For each function with input argument n, determine the precise number of “fun

Question

3) For each function with input argument n, determine the precise number of “fundamental operations” that will be executed. Your answer should be a function of n in closed form. Note that “closed form” means that you must resolve all ’s and ’s. An asymptotic answer (such as one that uses big-oh, big-theta, etc.) is not acceptable. Assume that n 1 for all parts. Note that fc is recursive. This problem asks for the exact count of “fundamental operations”, but for this class, also give a good Big-Oh O bound.

a) void fa (int n) l for (int i = 0; i = n; i = i+2) Perform 1 fundamental operation; //endfor i b) void fb (int n) i for (int j //endfor j for (int k = 2; k = n; k++) 1, j n; j++) Perform 1 fundamental operation; //endfor k

Explanation / Answer

a)

The precis number of times the fundamental operation is executed depends on how many times the loop runs and which in turn depends on value of n .

Since , the loop starts from 0 and ends when it is equal to n . It is incremented by 2 every time . So , the exact number is

(n/2)+1

The +1 is because it starts from 0 , and ends only when it is equal to n . Note here 0 is included as the initial value .

b)

Similarly , the number of times the fundamental operation runs depends on both the for loops , and the value of .

Consider the first 'for' loop , k starts from 2 and ends when it is equal to n , with n inclusive . So the loop runs for

(n-1) times . The second 'for' loop , j starts from 1 and ends when the value of j is 1 less than n . So this loop also runs (n-1) times . The number of times the fundamental operation runs is product of the times the first loop and second loop runs , because they are nested loops . For each instance of the first loop the second loop runs (n-1) times .

Hence ,

(n-1)*(n-1) = n2-2n+1 .

Is the exact number of times.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.