Consider the following segment of C-code:int j, n;j = 1;while (j <...
may be we have to count those comparisons which results in the execution of loop.
Answer should be Ceil(log2n) + 1
EDIT: but answer could be: floor(log2n) + 2
View all questions of this test
Consider the following segment of C-code:int j, n;j = 1;while (j <...
The given C code segment is as follows:
```
int j, n;
j = 1;
while (j = n)
j = j * 2;
```
This code segment initializes two variables, `j` and `n`, and assigns the value 1 to `j`. It then enters a while loop that continues as long as the value of `j` is equal to the value of `n`. Within the loop, the value of `j` is multiplied by 2.
The correct answer to determine the time complexity of this code segment is option 'A' - [log2n] 1. Let's understand why this is the case.
1. Analysis of the code segment:
- The variable `j` is initially set to 1.
- The while loop condition checks if `j` is equal to `n`.
- If `j` is equal to `n`, `j` is multiplied by 2.
- The loop continues as long as `j` is equal to `n`.
2. Execution of the code segment:
- Since `j` is initialized as 1, the loop will execute at least once.
- In each iteration of the loop, `j` is multiplied by 2.
- Therefore, the value of `j` will keep increasing exponentially.
3. Termination condition:
- The loop will terminate when the value of `j` is no longer equal to `n`.
- Since `j` is increasing exponentially, it will eventually become larger than `n`, breaking the loop.
4. Time complexity analysis:
- The loop will execute until `j` becomes larger than `n`.
- The value of `j` in each iteration can be represented as 2^k, where k is the number of iterations.
- The loop will terminate when 2^k > n.
- Taking the logarithm base 2 on both sides of the inequality, we get k > log2n.
- Therefore, the loop will execute log2n + 1 times.
5. Conclusion:
- The time complexity of this code segment is O(log2n) because the loop executes log2n + 1 times, which can be approximated as O(log2n).
- Hence, the correct answer is option 'A' - [log2n] 1.
Consider the following segment of C-code:int j, n;j = 1;while (j <...
J=1 j=1*2. 2^0=1
j=2. j=2*2. 2^1=2
j=4. j=4*2 2^2=4
j=8. j=8*2. 2^3=8
j=16. j=16*2. 2^4=16
j=n. 2^k=n
(taking log↓2 both side)
log2 2^k = log2 n
( log2 and 2 got cancelled)
k= log2 n. is. O( log2 n ) of the code but
the exact time complexity is log2 n +1
becoz condition failed one time and loop terminated at this point .