Time complexity

def f()

ans = 0

for i = 1 to n:

for j = 1 to log(i):

ans += 1

print(ans)

Time Complexity of this program:

• O(n)

• O(nlogn)

• O(n^2)

• O(n^3)

def f():

a = 0

for i = 1 to n:

a += i;

b = 0

for i = 1 to m:

b += i;

Time Complexity of this program:

• O(n)

• O(m)

• O(n+m)

• O(n∗m)

def f():

a = 0

for i = 1 to n:

a += random.randint();

b = 0

for j = 1 to m:

b += random.randint();

Time Complexity of this program:

• O(n)

• O(m)

• O(n+m)

• O(n∗m)

def f():

int a[n][n]

// Finding sum of elements of a matrix that are above or on the diagonal.

sum = 0

for i = 1 to n:

for j = i to n:

sum += a[i][j]

print(sum)

Time Complexity of this program:

• O(n)

• O(nlogn)

• O(n^2)

• O(n^3)

def f():

int a[n][n]

sum = 0

// Finding sum of elements of a matrix that are strictly above the diagonal.

for i = 1 to n:

for j = i to n:

sum += a[i][j]

print(sum)

for i = 1 to n:

sum -= a[i][i]

Time Complexity of this program:

• O(n)

• O(nlogn)

• O(n^2)

• O(n^3)

def f():

ans = 0

for i = 1 to n:

for j = n to i:

ans += (i * j)

print(ans)

Time Complexity of this program:

• O(n)

• O(nlogn)

• O(n^2)

• O(n^3)

def f():

int a[N + 1][M + 1][K + 1]

sum = 0

for i = 1 to N:

for j = i to M:

for k = j to K:

sum += a[i][j]

print(sum)

Time Complexity of this program:

• O(N+M+K)

• O(N∗M∗K)

• O(N∗M+K)

• O(N+M∗K)

def f(n):

ans = 0

while (n > 0):

ans += n

n /= 2;

print(ans)

Time Complexity of this program:

• O(logn)

• O(n)

• O(nlogn)

• O(n^2)

def f(n):

ans = 0

while (n > 0):

ans += n % 10

n /= 10;

print(ans)

Time Complexity of this program:

• O(log_2​n)

• O(log_3​n)

• O(log₁₀n)

• O(n)

def f():

ans = 0

for (i = n; i >= 1; i /= 2):

for j = m to i:

ans += (i * j)

print(ans)

Time Complexity of this program:

• O(n+m)

• O(n∗m)

• O(mlogn)

• O(nlogm)