Give a tight bound of the nearest runtime complexity class for each of the following code fragments in Big-Oh notation, in terms of the variable N. In other words, write the code's growth rate as N grows. Write a simple expression that gives only a power of N using a caret ^character for exponentiation, such as O(N^2) to represent O(N2) or O(log N) to represent O(log2 N). Do not write an exact calculation of the runtime such as O(2N3 + 4N + 14).
Give a tight bound of the nearest runtime complexity class for each of the following code fragments in Big-Oh notation, in terms of the variable N. In other words, write the code's growth rate as N grows. Write a simple expression that gives only a power of N using a caret ^character for exponentiation, such as O(N^2) to represent O(N2) or O(log N) to represent O(log2 N). Do not write an exact calculation of the runtime such as O(2N3 + 4N + 14).
Part C)
The outer loop runs 1000000 times, and each iteration of the outer loop takes O(1000000^2) time due to the three nested loops.
The first and second nested loops both have time complexity O(1000000), and the third nested loop has time complexity O(i), with the maximum value of i being 1000000.
Finally, the code adds N to the value of sum inside the inner loops, so the overall time complexity is O(N * 1000000^3).
Therefore, time complexity of the code is O(N * 1000000^3), where N is the value assigned to the sum variable.
--> which can simplified as in terms as N as : O(N)
Answer: O(N)
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
