Q1.
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:
- A. O(N + M + K)
- B. O(N * M * K)
- C. O(N * M + K)
- D. O(N + M * K)
Q2.
def f(n):
ans = 0
while (n > 0):
ans += n
n /= 2;
print(ans)Time Complexity of this program:
- A. O(log(n))
- B. O(n)
- B. O(n * log(n))
- C. O(n^2)
Q3.
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:
- A. O(n+m)
- B. O(n∗m)
- C. O(m * log(n))
- D. O(n * log(m))
Q4.
def f():
ans = 0
for (i = n; i >= 1; i /= 2):
for (j = 1; j <= m; j *= 2)
ans += (i * j)
print(ans)Time Complexity of this program:
- A. O(n * m)
- B. O(log(m) * log(n))
- C. O(m * log(n))
- D. O(n * log(m))
Q5. // Finding greatest common denominator of two numbers a, b.
def gcd(a, b):
if (a < b) swap(a, b)
if (b == 0) return a;
else return gcd(b, a % b)Time Complexity of this program:
Let n = max{a,b}
- A. O(1)
- B. O(logn)
- C. O(n)
- D. O(n^2)
Q6. // Binary searching in sorted array for finding whether an element exists or not.
def exists(a, x):
// Check whether the number x exists in the array - a.
- lo = 0, hi = len(a) - 1
- while (lo <= hi):
- mid = (lo + hi) / 2
if (a[mid] == x): return x;
else if (a[mid] > x): hi = mid - 1;
else lo = mid + 1;
return -1; // Not found.Time Complexity of this program:
Let n = len(a)n=len(a)
- A. O(1)
- B. O(logn)
- C. O(n)
- D. O(n^2)