Question

Algorithmic Complexity: what is the asymptotic complexity (Big-O) of each code section? Identify the critical section of each.\ Line 1: for (int i=0; i<532; i++) { f(n) = O( ) Line 2: for (int j=1; j

Answer 1

Answer:

Check the explanation

Explanation:

1) f(n) = O( 1 ), since the loops runs a constant number of times independent of any input size

there is no critical section in the code, as a critical section is some part of code which is shared by multiple threads or even processes to modify any shared variable.This code does not contain any variable which can be shared.

2) f(n) = O( log n! ), the outer loop runs for n times, and the inner loop runs log k times when i = k,ie the total number of print will be – log 1 + log2 +log3 +log4+…...+ log n = log (1 . 2 . 3 . 4 . ……. . n ) =log n!

there is no critical section in the code, as a critical section is some part of code which is shared by multiple threads or even processes to modify any shared variable.This code does not contain any variable which can be shared.

Note : Log (m *n) = Log m + Log n : this is property of logarithm

3) f(n) = $O( n^2 )$, since both outer and inner loop runs n times hence , the total iterations of print statement will be : n +n+n+…+n

for n times, this makes the complexity – n * n = n2

there is no critical section in the code, as a critical section is some part of code which is shared by multiple threads or even processes to modify any shared variable.This code does not contain any variable which can be shared.