Skip to content

Instantly share code, notes, and snippets.

@nonsocode
Last active November 24, 2022 21:45
Show Gist options
  • Save nonsocode/1b7ab15945538dde12bd5c328a26cc37 to your computer and use it in GitHub Desktop.
Save nonsocode/1b7ab15945538dde12bd5c328a26cc37 to your computer and use it in GitHub Desktop.
Time complexity

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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment