Homework SourseThis assignment involves either writing a program to impleme
This assignment involves either writing a program to implement the question #34 (textbook) or using the paper-and-pencil which will calculate the time complexity of the while loops. You may write your code in a contemporary language of your choice; typical languages would include C/C++, Java, Ada, or Pascal. The algorithm is described in the textbook. #34 (page 48) What is the time complexity T(n) of the nested loops below? For simplicity, you may assume that n is a power of 2. That is, n = 2 k for some positive integer k. You MUST show your work in detail.
…
…
i = n;
while (i >= 1){
j = i;
while (j <= n){
<body of the while loop> //Needs (1)
j = 2 * j;
}
i = i/2 ;
}
…
…
Input: The size of input n. Output: You must submit a hard copy of your well-commented source program and your printed output if any. Please show your program in the classroom after the submission.
Output: You must submit a hard copy of your well-commented source program and your printed output if any. Please show your program in the classroom after the submission.
MUST BE DONE IN JAVA WITH COMMENTS.
Solution
O (log n * log n)
Since the outer loop (i) runs for log n times (because is reduced to half in every iteration) and the inner loop (j) runs for log n times similarly.
