Level 0 - Week 2

📄 | Weekly sheet

• Sheet link

🗃️ | Materials

✨ | Tips and Tricks session

Complexity

1) The complexity of the following code is:

int a = 5;
int b = 7;
int c = 4;
int d = a + b + c + 153;

• $ a) \quad \mathcal{O}(1)$

• $ b) \quad \mathcal{O}(n)$

• $ c) \quad \mathcal{O}(nm)$

• $ d) \quad \mathcal{O}(n^2)$

Answer

$ a)\: \mathcal{O}(1)$, because it executes a constant number of operations.

---

2) The complexity of the following code is:

for (int i = 1; i <= n; i++) {
	// constant time code here
}

• $ a) \quad \mathcal{O}(1)$

• $ b) \quad \mathcal{O}(n)$

• $ c) \quad \mathcal{O}(n!)$

• $ d) \quad \mathcal{O}(n^2)$

Answer

$ b)\: \mathcal{O}(n)$, Because the time complexity of loops is the number of iterations that the loop runs

---

3) The complexity of the following code is:

int i = 0;
while (i < n) {
	// constant time code here
	i++;
}

• $ a) \quad \mathcal{O}(n)$

• $ b) \quad \mathcal{O}(1)$

• $ c) \quad \mathcal{O}(nm)$

• $ d) \quad \mathcal{O}(n^2)$

Answer

$ a)\: \mathcal{O}(n)$, Because the time complexity of loops is the number of iterations that the loop runs

---

4) The complexity of the following code is:

for (int i = 1; i <= 5 * n + 17; i++) {
	// constant time code here
}

• $ a) \quad \mathcal{O}(1)$

• $ b) \quad \mathcal{O}(n^3)$

• $ c) \quad \mathcal{O}(\sqrt{n})$

• $ d) \quad \mathcal{O}(n)$

Answer

$ d)\: \mathcal{O}(n)$, Because we ignore constant factors and lower order terms

5) The complexity of the following code is:

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= m; j++) {
		// constant time code here
	}
}

• $ a) \quad \mathcal{O}(1)$

• $ b) \quad \mathcal{O}(n)$

• $ c) \quad \mathcal{O}(nm)$

• $ d) \quad \mathcal{O}(n^2)$

Answer

$ c)\: \mathcal{O}(nm)$ , because the outer loop runs $\mathcal{O}(n)$ iterations and the inner loop $\mathcal{O}(m)$ .

6) The complexity of the following code is:

for (int i = 1; i <= n; i++) {
	for (int j = i; j <= n; j++) {
		// constant time code here
	}
}

• $ a) \quad \mathcal{O}(1)$

• $ b) \quad \mathcal{O}(n)$

• $ c) \quad \mathcal{O}(nm)$

• $ d) \quad \mathcal{O}(n^2)$

Answer

$ a)\: \mathcal{O}(n^2)$,because the outer loop runs $\mathcal{O}(n)$ iterations and the inner loop $\mathcal{O}(n)$

7) The complexity of the following code is:

for (int i = 1; i <= n; i++) {
	for(int j = 1; j <= n; j++) {
		// constant time code here
	}
}
for (int i = 1; i <= n ; i++) {
	// more constant time code here
}

• $ a) \quad \mathcal{O}(1)$

• $ b) \quad \mathcal{O}(n)$

• $ c) \quad \mathcal{O}(nm)$

• $ d) \quad \mathcal{O}(n^2)$

Answer

$ d)\: \mathcal{O}(n^2)$, becauseIf an algorithm contains multiple blocks, then its time complexity is the worst time complexity out of any block

8) The complexity of the following code is:

int n;
while(n > 0){
  if(n % 2 == 0){
    cout << 0;
  }
  else{
    cout << 1;
  }
  n /= 2;
}

• $ a) \quad \mathcal{O}(1)$

• $ b) \quad \mathcal{O}(n)$

• $ c) \quad \mathcal{O}(\log_{2}{n})$

• $ d) \quad \mathcal{O}(n^2)$

Answer

$ c)\: \mathcal{O}(\log_{2}{n})$, Because in each iteration in the loop we divide n by 2

✨ | Contest Up solve

✏️ | Sheet up solve

A.1 to N

B. Even Numbers

C. Even, Odd. Positive and Negative

D. Fixed Password

E. Max

F. Multiplication table

G. Factorial

H. One Prime

I. Palindrome

J. primes from 1 to n

k. Divisors

L. GCD

M. Lucky Numbers

N. Numbers Histogram

O. Pyramid

P. Shape1

Q. Digits

R. Sequence of Numbers and Sum

S. Sum of Consecutive Odd Numbers(video 1)

S. Sum of Consecutive Odd Numbers(video 2)

T. Shape2

U. Some Sums

V. PUM

W. Shape3

X. Convert To Decimal 2

Y. Easy Fibonacci

Z. Three Numbers