Basics of Time & Space Complexity

# Basics of Time & Space Complexity --- title: Agenda description: duration: 300 card_type: cue_card --- ## Content - Arithmetic & Geometric Progression - Time Complexity - Big O notation - Comparison of order of time complexities - Space Complexity --- title: Arithmetic & Geometric Progression description: duration: 1800 card_type: cue_card --- ## Basic mathematical prerequisites - ### Concept 1 For the following series on some number N, how many steps it'll take to reach 1? N -> N/2 -> N/4 -> N/8 -> ..... -> 1 <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/064/973/original/i.png?1707903779"> ### Concept 2 Given two numbers say 3 and 10, how many numbers are in between those numbers (inclusive)? <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/064/974/original/2.png?1707903954"> ### Concept 3 (`Arithmetic Progression`) What is the sum of `N` numbers of AP? <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/064/976/original/3.png?1707904203"> ### Concept 4 (`Geometric Progression`) What is the sum of `N` terms of a GP? <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/064/977/original/4.png?1707904266"> #### Some useful logarithm properties - log*a*(*a*)*x* = *x* --- title: Quiz-1 description: Quiz-1 duration: 60 card_type: quiz_card --- # Question What will be the sum of 7 terms of the following series? 1, 3, 9, 27, 81, ...... # Choices - [ ] 100 - [x] 1093 - [ ] 1092 - [ ] 3280 --- title: Time Complexity description: duration: 4500 card_type: cue_card --- ## Time Complexity Time complexity is a measure of the efficiency of an algorithm, describing the relationship or trend between the number of operations performed by the algorithm and the size of its input. - It's a representation of time complexity, explaining the growth rate of an algorithm's running time as the input size increases. - It specifically focuses on the trend, ignoring constant factors and coefficients. - In `Big O notation`, only the polynomial term with the highest power is considered relevant. #### Question: What will be the time complexity of the following program? def fun(N): s = 0 for i in range(1, N+1): s += i return s <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/064/990/original/5.png?1707907263"> **Note:** Basically O represents the order in which we can bound the time complexity of the algorithm. <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/064/991/original/6.png?1707907588"> We primarily focus on the majority function due to its ability to prioritize significant contributions, particularly with large values of N. In the given example, only factors of substantial magnitude, such as the distance from Earth to the Moon, are considered relevant. #### Question: What will be the time complexity of the following program? ```python= def fun(N, M): s = 0 for i in range(1, N+1): s += i for j in range(1, M+1): s += j return s ``` <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/064/992/original/7.png?1707907678"> #### Question: What will be the time complexity of the following program? ```python= def fun(N): i = 1 while i < N: i += 2 ``` <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/064/995/original/8.png?1707907989"> **Note:** Constant terms, coefficients are ignored. Only the order of magnitude matters. #### Question: What will be the time complexity of the following program? ```python= def fun(N): s = 0 for i in range(1, 101): s += i return s ``` In this case, since the number of iterations remains unchanged regardless of the input, this is an example of constant time complexity, denoted as `O(1)`. #### Question: What will be the time complexity of the following program? ```python= def fun(N): s = 0 for i in range(1, int(N**0.5)): s += i return s ``` Here, the number of iterations are sqrt(N). Hence, the time complexity is `O(sqrt(N))`. #### Question: What will be the time complexity of the following program? ```python= def fun(N): i = N while i >= 1: i = i // 2 ``` <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/064/996/original/9.png?1707908455"> #### Question: What will be the time complexity of the following program? Code ```python= def fun(N): i = 0 while i <= N: i = i * 2 ``` In this scenario, the value of i remains fixed at 0 throughout each iteration, leading to an infinite loop. This example highlights the importance of considering the iterative process and its implications. #### Question: What will be the time complexity of the following program? ```python= def fun(N): i = 1 while i <= N: i = i * 2 ``` <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/064/998/original/10.png?1707908807"> #### Question: What will be the time complexity of the following program? ```python= def fun(N): s = 0 for i in range(N): for j in range(N): s += j return s ``` <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/064/999/original/11.png?1707908904"> #### Question: What will be the time complexity of the following program? ```python= def fun(N): s = 0 for i in range(10): for j in range(N): s += j return s ``` <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/065/002/original/12.png?1707909045"> #### Question: What will be the time complexity of the following program? ```python= def fun(N): s = 0 for i in range(N): j = 1 while j <= N: j = j * 2 return s ``` <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/065/004/original/14.png?1707909210"> #### Question: What will be the time complexity of the following program? ```python= def fun(N): s = 0 for i in range(N): for j in range(N): s += j for i in range(N): s += i return s ``` <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/065/005/original/15.png?1707909314"> We can disregard the magnitude terms within addition and solely concentrate on the term with the highest order of magnitude. However, we must not overlook any terms if they are being multiplied. #### Question: What is the Big O form of the following time complexity iterations? 100*N*2 + 32*N*3 + 51*N* + 1000 **Answer:** `32(N^3)` --- title: Break & Doubt Resolution description: duration: 600 card_type: cue_card --- ### Break & Doubt Resolution `Instructor Note:` * Take this time (up to 5-10 mins) to give a short break to the learners. * Meanwhile, you can ask the them to share their doubts (if any) regarding the topics covered so far. --- title: Quiz-2 description: Quiz-2 duration: 60 card_type: quiz_card --- # Question Consider the following Python code snippet. What is the time complexity of this code? ```python= def example_function(arr): total = 0 for i in range(len(arr)): for j in range(i + 1, len(arr)): k = 1 while k <= len(arr): total += i + j + k k *= 2 return total ``` # Choices - [ ] O(n^2) - [x] O(n^2 log n) - [ ] O(n log n) - [ ] O(2^n) --- title: Comparison of order of time complexities description: duration: 600 card_type: cue_card --- ## Comparison of order of time complexities - <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/065/006/original/16.png?1707909694"> <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/065/007/original/17.png?1707909740"> --- title: Space Complexity description: duration: 900 card_type: cue_card --- ## Space Complexity - Space complexity in Python refers to the amount of memory a program needs to complete its execution. - It is the analysis of memory usage with respect to the input size. - Similar to time complexity, space complexity is also expressed using `Big O` notation. #### Question: What will be the space complexity of the following program? Code ```python= def fun(N): s = 0 for i in range(1, N+1): s += i return s ``` This code utilizes constant space complexity as it does not allocate any additional memory corresponding to the size of the input. <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/065/008/original/18.png?1707909915"> #### Question: What will be the space complexity of the following program? ```python= def fun(N): s = [0]*N for i in range(1, N+1): s[i] = i return sum(s) ``` Here, an additional list is created with the same size as the input, resulting in an extra order of N space being consumed. <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/065/009/original/19.png?1707910041"> --- title: Quiz-3 description: Quiz-3 duration: 60 card_type: quiz_card --- # Question Consider the following Python code snippet. What is the space complexity of this code? Code ```python= def find_max(arr): max_value = arr[0] for value in arr: if value > max_value: max_value = value return max_value find_max([3, 1, 4, 1, 5, 9, 2, 6]) ``` # Choices - [ ] O(n^2) - [ ] O(n) - [ ] O(n log n) - [x] O(1) --- title: Practice Coding Question(s) description: duration: 600 card_type: cue_card --- ### Practice Coding Question(s) You can pick the following question and solve it during the lecture itself. This will help the learners to get familiar with the problem solving process and motivate them to solve the assignments. Make sure to start the doubt session before you start solving the question. Q. https://www.scaler.com/hire/test/problem/22400/