some java questions recursion and order of an equation

Guru Ji
Guru Ji used Ask the Experts™
on
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?




Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
for question 1, the runtime equation has to do with the approximate running time of the algorithm, based on the number of lines of code run for a given sample size, thus:

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

Author

Commented:
it is one of my past exams which I have it, so I just typed it in exactly...

Can you please write me the non-recursive method of the last question...

and please tell me what would be the run time equation will be ?

Thanks
Non recursive method:

private void Insert_End (node ptr, Data data){
    node cur = ptr;

    while (cur.next != null) {
        cur = cur.next;
    }

    cur.next = Create_Node(ptr.data);  
 }
Although I'm pretty sure what you meant to type (in the question) was Create_Node(Data) so

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

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial