Jump to content
Urch Forums

Driller on software systems: doubts


Nkruti

Recommended Posts

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

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

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?

Link to comment
Share on other sites

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

 

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

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.

 

 

 

 

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...