Tiêu đề Iterative Time Complexity - TAP [Summer 2025].docx ✅

Time Complexity RAM (Random Access Machine) Model: RAM model helps us to analyze Algorithms- ● An abstract simplified computational model where instructions can not run parallelly as this is a single processor system. ● Each simple operation takes 1 time step. For example, instructions like Assignment, Data Access, Comparison, Control flow (return), Arithmetic operations (+, -, *, /) take constant time [O(1)]. Loops are not simple operations. ● Each memory access takes one time step and there is no shortage of memory. Constant Time Complexity: 1. x = 10 if x > 0: print(“Positive”) else: print(“Negative”) Time complexity = O(1) [constant time] 2. if (condition) { i = 0; } else { for ( j = 0; j < n; j++) { a[j] = j; } } if -> O(1) else -> O(1) + O(n) = O(n) Time complexity = max(O(1), O(n)) = O(n) 3. if a > 20 { print “yes”
} else { print(“no”) } Time complexity = O(1) [constant time] 4. multiplier (int a, int b) { c = a * b return c } Time complexity = O(1) [constant time] 5. i = 1 c = 10 while i < n: c = c*10 i = i + n print(c) Time complexity = O(1) [constant time] Linear Time Complexity: 6. max = input() for i in range(0, n-1): temp = input() if temp > max: max = temp print(max) Time complexity = O(n) [Linear time] 7. Sum (A, n) { s = 0; for (i=0; i<n; i++) {
s = s + A[i]; } return s; } Sum (A, n) { s = 0; …………………………………………. 1 for (i=0; i<n; i++) { ……….……………………. n+1 s = s + A[i]; …………………………… n*1 } return s; ………………………………………. 1 } —---------------------- f(n) = 1+n+1+(n*1)+1 = 2n + 3 The degree of the polynomial is 1. Time complexity = O(n) 8. for i in range(0, n): c = c + 1 for j in range(0, n): c = c + 1 print(c) Time complexity = O(n) [Linear time] 9. i = n while i >= 1{ print(i); i = i - 5 } for (i=n; i>=1; i=i-5){ print(i) } Iteration i
0 n = n - (0*5) 1 n-5 = n - (1*5) 2 n-10 = n - (2*5) 3 n-15 = n - (3*5) . . . . . . k n - (k*5) The loop will terminate when i < 1. So, n - (k*5) < 1 Let, n - (k*5) = 1 ⇒ k*5 = n - 1 ⇒ k = (n - 1) / 5 Time complexity = O(n) 10. i = 1 c = 10 while i < n: c*=10 i+=20 print(c) Time complexity = O(n) [Linear time] Quadratic Time Complexity: 11. for i in range(n): for j in range(n): c+=1 print(c) Time complexity = O(n 2 ) [quadratic time] 12.