This assignment involves either writing a program to implement the question #34
ID: 3783493 • Letter: T
Question
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.
Explanation / Answer
begin
Input: n(pos. Integer)
Output: y(pos. Integer)
Other: x,z(pos. Integer)
x:= 2*n
y := 0;
while x>0 do
y:=y+1;
z:=0;
while z<2 do
x := x - 1;
z := z+1;
end