Driller on software systems: doubts

[Nkruti]

These questions are with regard to a previous posting http://www.TestMagic.com/forum/topic.asp?TOPIC_ID=8681

What is the value of f(n) in big-O notation?

function f(n) {
if (n <= 1) return 1;
return f(n/2) + 2*f(n/4);
}


Should'nt the answer be O(nlogn)?
__________________________________________________ _

Q12) What does the following program print?


int x = 1;
function f(i) {
int x = 2;
I *= 3;
for (int j = 1; j <= i; j++)
g(j);
}

function g(j) {
print j+x;
}
f(x);



Consider four scenarios: dynamic scope with pass-by-value, dynamic scope with pass-by-reference, static scope with pass-by-value, static scope with pass-by-reference.

Dynamic scope
Pass by value: 3 4 5
Pass by reference: 3 4 5

Static scope
Pass by value: 2 3 4
Pass by reference: 4 5 6
__________________________________________________ _______
I think the answer to static scope with pass by reference should be 2 3 4

Could someone comment?

[dionysus]

Yes, Nkruti. The answer is O(n log n). With the following explanation:

f(n) = f(n/2) + 2 f(n/4) if n > 1 and is 1 if n <=1.

Now, guess f(n) = c n log n + d n as the solution, which would imply that f(n) = O(n log n). Substituting, we get:

c n log n + d = c (n/2) log (n/2) + d n + 2 (c (n/4) log (n/4) + d n) if N > 1 and c 1 log 1 + d 1 = d = 1 if n = 1. So therefore we get d = 1.

From the first equation:
c n log n + d n = c (n/2) log (n/2) + d n + c (n/2) log (n/4) + 2d n
=> c n log n + d n = c (n/2) (log (n/2) + log (n/4)) + 3d n
=> c n log n = c (n/2) log (n^2/8) + 2d n
=> c n log n = c (n/2) (log n^2 - log 8) + 2d n
=> c n log n = c n log n - c (n/2) log 8 + 2d n.
Therefore, we get c (n/2) log 8 = 2d n. Putting d = 1, we have:
c = 2 * 2 / log 8 = 4 / log 8 = some constant.
So f(n) = O(n log n).

Also, the answer of static scoping with pass by reference is indeed 4,5,6. I think you misunderstood the line

I *= 3;

because it really is
[blue]

i *= 3;

[blue]
To understand that, in static scoping, you can safely rename the outer x with a y. So the function body now looks like:

int y = 1;
function f(i) {
int x = 2;
i *= 3;
for (int j = 1; j <= i; j++)
g(j);
}

function g(j) {
print j+y;
}
f(y);

Now, f(y) = f(1), so that the referenced variable I in the function f is 1, but subsequently it is multiplied by 3, so that I = 3 and therefore y = 3 since the variable is passed by reference. So calls to g as g(1), g(2), g(3) would result in 1 + 3, 2 + 3 and 3 +3 = 4, 5, 6. Which is the answer.

[blah321]

f(n) = f(n/2) + 2*f(n/4)
Isn't f(n) = cn ?

If we assume f(n) = cnlogn + dn
f(n) = c(n/2)log(n/2) + d(n/2) + c(n/2)log(n/4) + d(n/2) ( = c(n/2)log(n^2/8) + dn )
=> cnlogn + dn = cnlogn - 3c(n/2) + dn
=> c=0 ?