Question

Find and explain the time complexity (Big-Oh notation) for the following code snippet? [Points: 6]

double y = 0;
for( int i = 1; i <= n; i++ ){
for(int j = 1; j <= m; j++){ y += j*log(2);
} }
If n=m then what will be time complexity of the above nested iteration in Q2.a? [Points: 2]
Find and explain the time complexity (Big-Oh notation) for the following code snippet? [Points: 6]
long y = 0L;
for( int i = 1; i <= n; i++ ){
for(int j = 1; j <= m; j++){ y += log(j);
} }
[Note: log(LxMxN)=logL+logM+lognN]
Find and explain the time complexity (Big-Oh notation) for the following code snippet? [Points: 6]
long y = 0L;
for( int i = 1; i <= n; i++ ){
for(int j = 1; j <= n; j++){
y += factorial(j); //where factorial is a function that calculates the factorial value
//of the given number
} }

Answer 1

The first and second snippets feature a nested loop with time complexities of O(n*m), which simplifies to O(n^2) when n equals m. The third snippet includes a factorial operation within the nested loop, resulting in a time complexity of O(n*n!) due to the factorial's growth rate for each iteration combined with the outer loop.

Step-by-step explanation:

When determining the time complexity of a code snippet, we look at the code's structure and the operations that grow with input size. We apply Big-Oh notation to express this growth rate.

Q2.a Time Complexity

For the first code snippet, the nested loop structure results in an overall time complexity of O(n*m), because there are two independent loops, one running n times and the other running m times. If we assume n=m, the complexity simplifies to O(n^2), as each loop will run n times.

Q2.b Time Complexity

Similarly, the second code snippet also features nested loops with the same constraints, leading to an identical time complexity of O(n*m), and consequently O(n^2), if n=m.

Q2.c Time Complexity

The third code snippet introduces a factorial calculation within the inner loop. Calculating the factorial of a number j has a time complexity of O(j), as it involves j multiplications. As j iterates from 1 to n, we sum up all these complexities to achieve O(n*n!), which is the factorial's growth for each iteration multiplied by n for the outer loop.