Scribd
Upload
42 views2 pages

Algo

The document discusses a pseudocode program that calls functions f(n) and g(n). It asks (a) to express the return value of g(n) in terms of n, (b) the time complexity of g(n), and (c) a recurrence relation for the number of lines printed by f(n). It then shows the work to solve the recurrence relation exactly for part (d).

Uploaded by

Saqib Tariq
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
42 views2 pages

Algo

The document discusses a pseudocode program that calls functions f(n) and g(n). It asks (a) to express the return value of g(n) in terms of n, (b) the time complexity of g(n), and (c) a recurrence relation for the number of lines printed by f(n). It then shows the work to solve the recurrence relation exactly for part (d).

Uploaded by

Saqib Tariq
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

This question is to be attempted individually.

Consider the following pseudocode: int f(int n) { if


(n>1) { f(n/2); f(n/2); for(int i = 1; i <= g(n); i++) { println("Hello world!"); } f(n/2); } } int g(int n)
{ int sum = 0; for(int i = 1; i <= n; i++) sum += i; return sum; } Here println() is a function that
prints a line of text. Assume n is a power of 2. (a) Express the return value of g(n) in terms of n.
[5 marks] (b) What is the time complexity of g(n), in terms of n and in big-O? [5 marks] (c) Let
T(n) be the number of lines printed by f(n). Write down a recurrence formula for T(n), including
the base case. [5 marks] (d) Solve the recurrence in (c), showing your working steps. For full
credit give the exact answer (not big-O) and do not use Master Theorem. [20 marks]

(a) in g(n) we are doing summation like

1+2+3+4...till n = n*(n+1)/2

hence return value is n*(n+1)/2

(b) since we are running the loop for i to n hence time complexiyt is O(n)

(c) here the recurrence formula is

T(n) = 2*T(n/2) + n*(n+1)/2 // as g(n) returns n*(n+1)/2

(d) here T(n/2) = 2*T(n/4)+ (n/2)*(n/2+1)/2

putting in equation abve we get

T(n) = 4*T(n/4) + n*(n+1)/2+ 2*n/2*(n/2+1)/2 = 4*T(n/4)+n*(n+1)/2+n*(n+1)/4

similarly we get the sum as


n*(n+1)/2 + n*(n+1)/4 + n*(n+1)/8 ....logn terms

= n*(n+1) [ 1/2+1/4+1/8... ] = n*(n+1)* [ 0.5^logn]

this is the exact answer!

You might also like