Select the appropriate BigOh notation from among O1 O n Onlg

Select the appropriate \"Big-Oh\" notation from among: O(1), O (n). O(nlg n). O(n^2). for the number of times that \"x = x + 1\" will be executed in exercises (a) to (d). for i = 1 to 3n x = x+1 for i = 1 to n for j - 1 to (2n - 1) for k = 1 to (3n - 2) x = x + 1 i = n while (i greaterthanorequalto 1) {for j = 1 to n x = x + 1 i = floor (i/2)//floor of a number is the largest integer//that is less than the number//E.G. floor(3.7) - 3; floor(10.43) - 10} if (x > 3) X = x+1 else x = x-1

Solution

While solving such questions, we need to consider the iteration of variable. \"How much unit variable is covering?\"

a) Since the iteration runs from 1 to 3n, complexity of the equation is O(3n). => O(n)

b) Here there are three variables so thte total effective iteration at the end of loop is :

n*(2n-1)*(3n-2) =O(n³ +X) where X is n in degree <=2 & constants.

Complexity of equation: O(n^3)

3) If we solve this loop, we will get the series as :

n + n/2 + n/4 ..... . Total iterations are is Sum of series = n/(1-1/2)= 2n

Complexity : O(n).