This question asks us to find the best and worst case running time and how we ha
ID: 3583078 • Letter: T
Question
This question asks us to find the best and worst case running time and how we have found it using mathematical equations. I do not remember the exact details because it was in an exam. The method took an input array and there were these three nested for loops, the last one running until k < 5. I understand that the assignment, initialization and loop condition checks have constant running time, what I do not understand is what is the RT for the third nested loop: O(n), log n, or O(1)?
Thank you.
int sum; for (int i 0: i n: i++) for int j 0 j i: j++) for (int k i: k 5: k++) System. out.print (a [k]Explanation / Answer
The RT for the third for loop:
Since third loop in independent of other two. It will only run upto k<5.
for n value 5 or more the third loop will run ,
5 times for i=0
4 times for i=1
3 times for i=2
2 times for i=3
1 time for i=4
for i>=5,
everytime condition fails and third loop will not execute.
So, maximum number of times third loop will run is 15 times. Which is constant number of
times.
Hence,
the RT for the third for loop is O(1).
Overall time complexity and what dominates:
int sum will execute 1 time
first loop will execute n+1 times
second loop will execute i+1 times
third loop will execute constant times.
system.out.print(a[k]) will execute for constant times.
So, overall running time is:
=>1+O(n)*O(n)*O(1)
=>O(n2)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.