owned this note
owned this note
Published
Linked with GitHub
# Basics of Time & Space Complexity
---
title: Agenda
description:
duration: 300
card_type: cue_card
---
### Agenda
- Time Complexity
- Big O notation
- Space Complexity
---
title: Time Complexity
description:
duration: 1800
card_type: cue_card
---
## <u>Time Complexity</u>
It 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.
<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/015/281/original/Screenshot_2022-09-28_at_9.33.43_AM.png?1664337868">
\
We don't measure algorithms in absolute time, we measure them using `CPU cycles`.
Let's say each statement here is an operation.
Code:
```python=
# example 1
def foo(n): # 1
x = 1 # 1
y = 2 # 1
z = 3 # 1
print(n) # 1
foo(1000)
```
Output:
100000
No matter how big our input is, the computer only performs 5 operations according to the above function.
Hence we can say that **the number of operation does not depend on the size of the input**.
So the cost of executing `foo()` is constant. Therefore, it's a constant time function.
Code:
```python=
# example 2
def foo(n):
for i in range(n):
print(i)
foo(5)
```
Output:
0
1
2
3
4
Here the number of operations that the function performs is linearly dependent on the input.
Hence, the cost of this `foo()` function is **Linear**.
Code:
```python=
# example 3
def foo(n):
for i in range(n):
for j in range(n):
print("WOW!")
foo(3)
```
Output:
WOW!
WOW!
WOW!
WOW!
WOW!
WOW!
WOW!
WOW!
WOW!
Here the number of operations that the function performs is directly proportional to the square of the input.
Hence, the cost of this `foo()` function is **Quadratic**.
\
For calculating time complexity, we only care about the term with the highest power.
```
C(f(x)) = x^n + x ^(n-1) + ..... 1
```
In this case, the time complexity will be only `x^n`.
#### Note: The constant terms and coefficients are totally disregarded in the time complexity functions.
***Explanation:***
* If we plot two equations that differ only by some constants.
<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/016/215/original/Screenshot_2022-10-12_at_9.47.36_AM.png?1665548245">
* Zooming out, we can see that for a really big input the significance of constants gets nullified.
<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/016/216/original/Screenshot_2022-10-12_at_9.47.47_AM.png?1665548325">
#### Note: We completely ignore the terms having powers of x that are less than the degree of time complexity function.
***Explanation:***
* If we plot two different parabolas having equations -
* x^2 + x + 5
* x^2
<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/016/217/original/Screenshot_2022-10-12_at_9.53.21_AM.png?1665548582">
* Again looking at bigger values of x, both parabolas are now in-differentiable.
<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/016/218/original/Screenshot_2022-10-12_at_9.53.31_AM.png?1665548598">
---
title: Big O notation
description:
duration: 900
card_type: cue_card
---
## Big O notation \[O(n)\]
* 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.
<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/015/282/original/Screenshot_2022-09-28_at_9.52.43_AM.png?1664338957">
#### Example:
<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/015/284/original/Screenshot_2022-09-28_at_9.55.08_AM.png?1664339102">
---
title: Quiz-1
description:
duration: 60
card_type: quiz_card
---
# Question
What does the time complexity *O*(*n*<sup>2</sup>) signify in context of an algorithm's performance?
# Choices
- [ ] The execution time of the algorithm decreases exponentially as the input size increases.
- [x] The execution time of the algorithm is directly proportional to the square of the size of the input.
- [ ] The execution time of the algorithm remains constant regardless of the size of the input.
- [ ] The execution time of the algorithm increases linearly as the input size increases.
---
title: Estimating Time Complexity of Simple Code
description:
duration: 900
card_type: cue_card
---
In this segment, we'll explore the methodology for estimating the time complexity of a code snippet by understanding its logical flow.
### Question 1
**Code:**
```python=
def func(arr):
a, b = arr[0], arr[1]
sum_ = a+b
sub_ = a-b
mul_ = a*b
return sum_+sub_+mul_
func([1,2,3,4,5])
```
**Explanation:**
As the functionality of the code remains independent of the size of the input array `arr`, the time complexity is constant, denoted as `O(1)`.
### Question 2:
**Code:**
```python=
def func(n):
count = 0
for i in range(n):
count += 1
return count
func(5)
```
**Explanation:**
* `func` contains a single `for` loop that iterates `n` times, with n being the input.
* Within each iteration, it performs a consistent amount of work (incrementing `count`).
* Therefore, the cumulative work is directly proportional to `n`, leading to a time complexity of `O(n)`.
### Question 3
**Code:**
```python=
def func(n):
count = 0
for i in range(n):
for j in range(n):
count += 1
return count
func(5)
```
**Explanation:**
* `func` comprises two nested `for` loops, both ranging from 0 to `n-1`.
* Within each iteration of the outer loop, the inner loop runs `n` times, culminating in a total of `n * n` iterations.
* Consequently, the time complexity is expressed as `O(n^2)`.
---
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: Estimating Time Complexity of Complex Code
description:
duration: 1500
card_type: cue_card
---
### Question 4
**Code:**
```python=
def function(n):
count = 0
while n > 1:
n = n // 2
count += 1
return count
function(8)
```
**Explanation:**
* In `func`, we start with a value `n` and repeatedly divide it by 2 until it becomes 1 or less.
* Let's denote the number of times we divide `n` by 2 as `k`.
* Mathematically, this can be expressed as:
$n \, \div \, 2^k \leq 1$
* To find `k`, we rearrange this equation to solve for `k`:
$2^k \geq n$
* Taking the `logarithm` to the `base 2` of both sides gives us:
$\log_2(2^k) \geq \log_2(n)$
* Since $\log_2(2^k) = k$, this simplifies to:
$k \geq \log_2(n)$
* The value of `k` represents the number of iterations in the while loop.
* The number of iterations is therefore proportional to the logarithm of `n` to the `base 2`.
* Hence, the time complexity of the function is `O(log n)`, where the base of the logarithm is 2.
This mathematical explanation shows how the time complexity of dividing a number by 2 in each step of a loop leads to a logarithmic time complexity, specifically `O(log n)` with `base 2`.
### Question 5
**Code:**
```python=
def function(n):
count = 0
for i in range(n):
j = 1
while j < n:
count += 1
j = j * 2
return count
function(8)
```
**Explanation:**
In `func`, there are two loops: an outer `for` loop and an inner `while` loop.
1. **Outer Loop Analysis:**
- The outer loop is a for loop that iterates `n` times.
- Therefore, the complexity contributed by the outer loop is O(n).
2. **Inner Loop Analysis:**
- The inner loop doubles the value of `j` in each iteration, starting from 1 and continuing until it is less than `n`.
- Let's determine how many times we can double a number starting from 1 before it becomes greater than or equal to `n`.
- We start with 1 and double it `k` times: $1 \times 2^k$.
- We want to find the smallest `k` such that $1 \times 2^k \geq n$.
- Taking logarithms to `base 2` on both sides, we get: $\log_2(2^k) \geq \log_2(n)$.
- Since $ \log_2(2^k) = k $, this simplifies to: $k \geq \log_2(n)$.
- Hence, the number of iterations for the inner loop is proportional to $\log_2(n)$, giving us a complexity of `O(log n)` for the inner loop.
3. **Combined Complexity:**
- Since the inner loop `O(log n)` is nested within the outer loop `O(n), we multiply their complexities.
- The combined time complexity is therefore `O(n) * O(log n)` = `O(n log n)`.
In summary, the function's time complexity is `O(n log n)` because the outer loop runs `n` times and the inner loop runs $\log_2(n)$ times for each iteration of the outer loop.
This combined effect results in a total of `n * log₂(n)` iterations.
---
title: Quiz-2
description:
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)):
total += arr[i] * arr[j]
return total
```
# Choices
- [x] O(n^2)
- [ ] O(n)
- [ ] O(n log n)
- [ ] O(2^n)
---
title: Space Complexity
description:
duration: 1200
card_type: cue_card
---
## <u>Space Complexity</u>
* 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.
\
Code:
```python=
# example 1
def foo():
x = 5
y = 10
result = x + y
return result
```
In this example, the space complexity is **constant** `O(1)` because the amount of memory used does not depend on the input size.
\
Code:
```python=
# example 2
def foo(n):
numbers = [i for i in range(n)]
return numbers
```
In this example, the space complexity is **linear** `O(n)` because the size of the list (numbers) scales with the input size n.
\
Code:
```python=
# example 3
def foo(n):
matrix = [[0] * n for _ in range(n)]
return matrix
```
In this example, a 2D matrix is created with dimensions n x n, leading to a **quadratic** space complexity of `O(n^2)`.
---
title: Quiz-3
description:
duration: 60
card_type: quiz_card
---
# Question
Consider the following Python code snippet. What is the space complexity of this 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.
<span style="background-color: pink;">Make sure to start the doubt session before you start solving the question.</span>
Q. https://www.scaler.com/hire/test/problem/22400/
Google Drive
Gist
Clipboard
Sign in with Wallet
