i just have a question which was in one of my exams

I am looking for answers please help Thanks !

Given the following algorithm in pseudo code, and the knowledge that for problem size 100 the "while loop" executes 100 times and the "for loop" 2 x 106 times.

1)

2) while (condition)

2.1)

2.2)

3) for (condition)

3.1)

3.2)

3.3)

3.4)

4)

5)

a) What is the runtime equation of this algorithm?

b) What is the order of this algorithm?

QUES 2 -----------------------------------

Part- a ) Given the following code, convert this into a non-recursive method.

private void Insert_End (node ptr, Data data){

if (ptr.next != null) {

Insert_End(ptr.next, data);

else

ptr.next = Create_Node(ptr.data);

}

}

Part-b ) - What is the runtime equation of the recursive and non-recursive code?

I am looking for answers please help Thanks !

Given the following algorithm in pseudo code, and the knowledge that for problem size 100 the "while loop" executes 100 times and the "for loop" 2 x 106 times.

1)

2) while (condition)

2.1)

2.2)

3) for (condition)

3.1)

3.2)

3.3)

3.4)

4)

5)

a) What is the runtime equation of this algorithm?

b) What is the order of this algorithm?

QUES 2 --------------------------

Part- a ) Given the following code, convert this into a non-recursive method.

private void Insert_End (node ptr, Data data){

if (ptr.next != null) {

Insert_End(ptr.next, data);

else

ptr.next = Create_Node(ptr.data);

}

}

Part-b ) - What is the runtime equation of the recursive and non-recursive code?

Do more with

EXPERT OFFICE^{®} is a registered trademark of EXPERTS EXCHANGE^{®}

a) The equation could be anything n + 2n or 2*n + 4*2(n+6) + 3 depending on what level of detail you think is necessary. You get the idea though. while loop runs n times, for 2 lines of code, and the for loop runs 2*106 times (n+6) for 4 lines of code, and then there are 3 additional lines of code run.

b) The order or big Oh notation is the highest order term based on problem size, which in this case is n. So the order is O(n)

2) Are you sure that's the actual question that was on your exam? It seems awfully unlikely that you remember the entire question and detailed code all by memory, just from it having been on your exam.

To convert it into a non-recursive method just use for loops where it would normally call itself, it's not that hard. The runtime equation for each can be determined in the same way as I showed you in the first question. just observe how many times each line is run.

--

Alain Bryden

private void Insert_End (node ptr, Data data){

node cur = ptr;

while (cur.next != null) {

cur = cur.next;

}

cur.next = Create_Node(ptr.data);

}

private void Insert_End (node ptr, Data data)

{

node Current = ptr;

while (Current.next != null)

Current = Current.next;

Current.next = Create_Node(Data);

}

The runtime equation for both the non recursive algorithm is n+2, or O(n)

The recursive one runs in O(n) as well, but it uses up O(n) space whereas the non recursive uses only constant space.

Alain

## Premium Content

You need an Expert Office subscription to comment.Start Free Trial