Question

discrete math

(1) (15 pts) Time Complexity Analysis 1) (5 pts) What is the time complexity of the following code segment? Explain your answer; otherwise, you can't get full mark from this question. for(int i=1; i<n; i*=2) { sum-0; sum++; Answer: 2) (5 pts) What is the time complexity of the following code segment? Explain your answer; otherwise, you can't get full mark from this question. for(int j=0; j<n; j++){ for (int k=0; k<n; k++) { for (int =0; i<n; i++) { sum-j***l; Answer: 3) (5 pts) What is the time complexity of the following code segment? Explain your answer; otherwise, you can't get full mark from this question. for (int i=0; i<n; i++) for (int i=0; i<n; i++) sum++; sum- Answer:

Answer 1

Sum = 0 for (int i= 1; i<n; i*=2) L rum tt; } Each time, 'i is complexity is the no of times the for loop gets executed doubled, this is done writy until the i is less than in (as long as i is lees than no > Complexity of logn ) is the number of times Y=1 doubled before it caceeds n'a can be [ logen for (int j =o; jcn; j++ & { for (int k = 0; k<n; K+ + 7 € for (int i=0; i<n; i++) { sunt = j*kti; } L } for each value of ? 'k this loop is created for n-times for each value of j', this for loop is executed 'n' time, loop is executed for Intines the first for - Time complexity 0 (23) °(nx nxn)

(3) If there are two ore more pleus of code independent to each exor other, then time complexity oq the whole code is the maximum of time complexities of its subparts ) for lint i=0; izn; i++) This for loop exentes suntt n-timer On for (int i=0; i<n; i++) This is executed sum 2 n-times are 002 Now these "for" loopes are seperate i .e; they independent of one another sa complexity O (m max (O(n), O(n)) In previous problem (2), the for-loops are dependent ine; one- for loop is present in another for loop, in such cases, complexity = product of complexities of all for Loops
If u have any doubts in the solution ask it as a comment, I will clarify