Description

Group assignment – only one submission per groups- to be uploaded by the group leader of a proxy
Theoretical Part:
1. (10 marks) What is the largest size n of problem which can be solved in one second by an algorithm with the following running time functions, in microseconds (1 second = 1,000,000
2 e) (log2n)log2n microseconds): a) log2n b) √n c) n d) n
2. (15 marks) Justify the following statements using the “big-Oh” definition:
a) (n+25)2 is O(n2) , and n2 is O((n+25)2)
b) n3 is NOT O(n2);
c) Given f1(n) is (n+25)2 , and f2(n) is n3 what is the big-Oh for f1(n) x f2(n)?

3. (15 marks) Give the asymptotic (“big-Oh”) running time complexity of the following algorithm, show all the work you have done.
Algorithm: ArrayMangle(A[ ], int n) Input: an array A, an integer n x = 0; for (i=0; i<=n-1; i++) { for (j=i; j<=n-1; j++) { x = x + A[j];
}
for (k=0; k<= n-1; k++) { for (j=0; j< =n-1; j++) {
x = x + A[j]*A[k];
}
}
}

Programming Part (preferably using Java):
What is the top element of the stack once the above file is completely processed?