#010 DS&A - Time and Space Analysis
Tags: algorithms, computerscience, datastructres
Published: 2020-09-19 18:29:10

# Introduction

Nothing to say more than hello 👋,
In Case your wondering who is this man in the banner it's the Khwarizmi the inventor of algorithms concept.
Make sure to follow because I will start more advanced series in future.

# Algorithms

## Time and Space Analysis

### Introduction to asymptotic

 In order to solve any problem in computer science we usually write a program , before writing program it's better to write it in formal description which is called Algorithm .

let's say we have a problem `P` we need to write a program , let's say we write it in c , to write program we need first to write an Algorithm , let's say `P` have many solutions `s1,s2,s3,s4....` the thing that will differ solution from another is `time` and `memory` , the science of it is called `Design  and analysis of algorithm`.

some of the notations used in Algorithms are these:

### Asymptotic notation

**Big(oh) represented by O**

![image-20200914233224043](https://i.loli.net/2020/09/15/93msi27PfBTuZAh.png)

if time Increasing as input increasing so the the worst  case or upper bound is `C*g(n)` and satisfy those conditions

```
f(n) <= C*g(n) ; n >= n0 ; c>0 , n0 >= 1
f(n) = O(g(n))
```

let's take this example

```
f(n) = 3n+2 and g(n) = n
f(n) = O(g(n))
f(n) <= C * g(n) , c > 0 , n0 >= 1
3n+2 <= c*n
take c = 4
3n+2 <= 4n => n >= 2
```

we can pick `g(n) = n^2 or n^3 ... n^n`because `f(n)` can be written with respect to `g(n)` but it is preferred to take the smallest one which is `n`

**Big omega represented by Ω**

![image-20200915171717083](https://i.loli.net/2020/09/15/qNC62udonMtTJk4.png)

```
f(n) >= C*g(n) ; n >= n0 ; c>0 , n0 >= 1
f(n) = O(g(n))
```

example

```
f(n) = 3n+2 and g(n) = n
f(n) = O(g(n))
f(n) >= C * g(n)
3n+2 >= c*n
take c = 1 and n0 >= 1
3n+2 = Ω(n)
```

example 2

```
g(n) = 3n+2 g(n)=n^2
3n+2 ?= Ω(n^2) 
3n+2 >= c*n^2 , n0
```

We can not find a `C` that satisfy this solution , so we need to pick things lower than `n` like `log(n)` or `log(log(n))`  

**Big theta represented by Θ**

![image-20200915172753442](https://i.loli.net/2020/09/15/FzKDeXuHIAx89q7.png)

```
f(n) = Θ(g(n))
c1*g(n) <= f(n) <= c2*gn(n) ; c1,c2 > 0 , n >= n0
```

example

```
f(n) = 3n+2 , g(n) = n
f(n) <= C2*g(n)
take c2 = 4
3n+2 <= 4n

f(n) >= c1*g(n)
take c1 = 1
3n+2 >= n , n0 >= 1
```

`O` this mean their is no bigger time than this , and it's called worst case.

`Ω` this mean their is no better time than this , and it's called best case.

`Θ` this mean it's the average case , and it's called the average case.

we usually don't care about best case , we care about worst case. If the worst and best cases are the same we generally go for average case.

example: take this array with `n` elements

| 0    | 1    | 2   | 3    |4    | 5    | 6   | 7   |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 5 | 7 | 1 | 2 | 4 | 10 | 20 | 11 |

let's say we need to find element `x`  , best case is `Ω(1)` , worst case is `O(n)`, average case is `Θ(n/2)= Θ(n)`

### Time Complexity Analysis

the `f(n)` is not the real time is just approximation  time that program take to finish.

there is 2 types of Algorithms :

```pseudocode
iterative:
A()
{
	for i=1 to n
		max(a,b)
}

recursive:

A(n)
{
	if() A(n/2)
}
```

any iterative can be written as recursive and vise versa.

If the Algorithm doesn't have loops or recursion time complexity is constant `O(1)` , if the time complexity is `O(n^2+n)` we take the biggest degree so we take it  `O(n^2)`

examples

```pseudocode
A()
{
	int i;
	for(i = 1 to n) pf("text");
}

time complexity : O(n)
```

```pseudocode
A()
{
	int i;
	for(i = 1 to n) 
		for(j = 1 to n)
			pf("omar");
}

time complexity : O(n^2)
```

```pseudocode
A()
{
	int i;
	while (s <= n)
	{
		i++;
		s = s+i;
		pf("omar");
	}
}

time complexity : O(sqrt(n))
/*
Analysing :
s : 1 3 6 10 15 21 ...
i : 1 2 3  4  5  6 ...
s will stop on n
let's say k is the final i
and s is nothing but new i + all old i (6 = 3+2+1) so it will stop when it reach
k(k+1)/2 > n
(k^2+k)/2 > n
k = O(sqrt(n))
*/
```

```pseudocode
A()
{
	int i;
	for(i=1;i^2<=n;i++) pf("omar");
}

time complexity : O(sqrt(n))
// Here all the cases are the same
```
```pseudocode
A()
{
	int i,j,k,n;
	for(i=1 ; i<n ; i++)
	{
		for(j=1;j<=i;j++)
		{
			for(k=1 ; k <= 100 ; k++)
			{
				pf("omar");
			}
		}
	}
}

time complexity : O(n^2)

/*
Analysing :
i = 1 , j = 1 time  , k = 100   times
i = 2 , j = 2 times , k = 200   times
i = 3 , j = 3 times , k = 300   times
...
i = n , j = n times , k = j*100 times

1*100+2*100+3*100+...+n*100 
 = 100 (1+2+3+...+n)
 = 100 (n(n+1)/2) = O(n^2)
*/
```

```pseudocode
int i,j,k,n;
for(i = 1 ; i <= n ;i++)
{
	for(j=1 ; j <= i^2 ; j++)
	{
		for(k=1 ; k <= n/2 ; k++)
		{
			pf("omar");
		}
	}
}

time complexity : O(n^4)

/*
Analysing :
i = 1 , j = 1 time  , k = n/2 * 1 
i = 2 , j = 4 times , k = n/2 * 4   
i = 3 , j = 9 times , k = n/2 * 9   
...
i = n , j = n^2 times , k = n/2 * n^2 times

n/2 * 1 + n/2 *4 + n/2 *  9 + ... + n/2 * n^2
 = n/2 * (n(n+1)(2n+1))/6
 = O(n^4)
*/
```

```pseudocode
A()
{
	for(i = 1 ; i < n ; i = i*2)
		pf("omar");
}

time complexity : O(log(n))

/*
Analysing :
i :  1  , 2   , 4	... n
    2^0 , 2^1 , 2^2 ... 2^k
2^k = n => k = log(n) = O(log(n))
since i is multiplied by 2 every step so log here is base 2
if i is multiplied by k we say log of base k
*/
```

```pseudocode
A()
{
	int i,j,k;
	for(i=n/2 ; i <= n ; i++)
		for(j=1 ; j <= n2 ; j++)
			for(k=1 ; k <= n ; k=k*2)
				pf("omar");
}

time complexity : O(n^2 * log(n))

/*
Analysing :
n/2 * n/2 * log(n) = O(n^2 * log(n))
*/
```

```pseudocode
A()
{
	int i,j,k;
	for(i=n/2 ; i <= n ; i++) // n/2
		for(j=1 ; j <= n ; i = 2*k) // log n
			for(k=1 ; k <= n ; k = k*2) // log n
				pf("omar");
}

time complexity : O(n*(log(n))^2)
```

```pseudocode
A()
{
	// assume n >= 2
	while(n>1)
	{
		n = n/2;
	}
}

time complexity : O(log(n))
```

```pseudocode
A()
{
	for(i = 1 ; i <= n ; i++) // n
		for(j = 1 ; j <= n ; i = j+i) // 
			pf("omar")
}

time complexity : O(n*log(n))

/*
Analysing :

i = 1 , j = 1 to n ; n   times
i = 2 , j = 1 to n ; n/2 times
i = 3 , j = 1 to n ; n/3 times
...
i = n , j = 1 to n ; n/n times

n(1+ 1/2 + 1/3 + ... + 1/n )
 = n (log n) = O(n * log(n))
*/
```

```pseudocode
A()
{
	int n = (2^2)^k;
	for(i=1;i<=n;i++) // n
	{
		j = 2
		while(j <= n)
		{
			j = j^2;
			pf("omar");
		}
	}
}

time complexity : O(log(log(n)))

/*
Analysing :

k = 1 ; n = 4  		; j = 2,4    			; n * 2 times
k = 2 ; n = 16 		; j = 2,4,16 			; n * 3 times
k = 3 ; n = (2^2)^3 ; j = 2^1,2^2,2^4,2^8 	; n * 4 times

n = (2^2)^k => log n = 2^k => log(log(n))=k
n*(k+1) = n(log(log(n)) + 1) = O(log(log(n)))
*/
```

### Time analysis of recursive

```pseudocode
A(n)
{
	if(...)
	return A(n/2)+A(n/2);
}

T(n) = c+2*T(n/2)
```

```pseudocode
A(n)
{
	if(n>1) return A(n-1);
}

T(n) = 1 + T(n-1) 
= 1 + 1 + T(n-2) 
= 2+1+T(n-3) 
= k+T(n-k) // k = n-1
= (n-1)+T(1) = n-1+1 = n
```

**back substitution**

```
T(n-1) = 1+T(n-2) -> 2
T(n-2) = 1+T(n-3) -> 3
```

```
T(n) = n + T(n)
T(n-1) = (n-1)+T(n-2)
T(n-2) = (n-2)+T(n-3)
-----------------------
T(n) = n + T(n-1)
	 = n + (n-1) + T(n-2)
	 = n + (n-1) + (n-2) + T(n-3)
	 = n + (n-1) + (n-2)+...+(n-k)+T(n-(k+1))
with n-(k+1)=1 => n-k-1=1 => k=n-2
= n+(n-1)+(n-2)+...+(n-(n-2))+T(n-(n-2+1))
= n+(n-1)+(n-2)+...+1
= n(n-1)/2
= O(n^2)
```

**recursive tree method**

```
T(n) = 2*T(n/2) + C ; n>1
	 = C ; n = 1
```

![image-20200917021118588](https://i.loli.net/2020/09/17/Uu1q7cTxwRBDoVM.png)

```
T(1) = T(n/n)
c+2c+4c+...+nc
c(1+2+4+...+n)
c(1+2+4+...+2^k)
c(1 (2^(k+1) - 1) / (2-1) )
c(2^k+1 - 1)
c(2n-1)
O(n)
```

---

```
T(n) = 2*T(n/2)+n ; n > 1
	 = 1 ; n = 1
```

![image-20200917025850624](https://i.loli.net/2020/09/17/KJNy5dLvGMYsO8t.png)

### comparing various functions

let's say we have two functions `n^2` and `n^3`  they have `n^2` as common so I rewrite it as `1` and `n` .

If `f(n)` is given and `g(n)` is given we take biggest degree and compare them. If they are constants like `2` and `4` we consider them the same.

examples

```
2^n							n^2
n log(2)					2 log(n)
n							2*log(n)
consider n = 2^100
2^100						2*log(2^100)
2^100						200
2^100 >>>>>>>>>>>>>>>>>>>	200
so 2^n growing very large
```

```
3^n							2^n
n*log(3)					n*log(2)
cancel n and compare it
log(3)						log(2)
```

```
n^2							n*log(n)
concel common terms
n*n							n*log(n)
n			>				log(n)
```

```
n							log(n)^100
log(n)						100*log(log(n))
take n = 2^128
128							100*log(128)
128							700
let's take n = 1024
1024						100*log(1024)
1024						1000
so n growing larger
```

```
n^log(n)					n*log(n)
log(n)*log(n)				log(n)+log(log(n))
for n = 10^1024
1024*1024					1034
for n = (2^2)^20		
2^20*2^20					2^20+20
so n^log(n) is larger
```

```
sqrt(log(n))				log(log(n))
1/2 * log(log(n))			log(log(log(n)))
take n = (2^2)^10
5							3.5
```

```
n^(sqrt(n))					n^log(n)
sqrt(n)*log(n)				log(n)*log(n)
sqrt(n)						log(n)
1/2 * log(n)				log(log(n))
n = 2^128
64							7
```

```
f(n) =  {
			n^3			0<n<10000
			n^2			n>=10000
		}
g(n) =  {
			n			0 < n < 100
			n^3			n > 100
		}
```

|      | 0-99 | 100-9999 | 10,000 .... |
| ---- | ---- | -------- | ----------- |
| f(n) | n^3  | n^3      | n^2         |
| g(n) | n    | n^3      | n^3         |

we take care about the function in infinity so `g(n)` is bigger in infinity

### Masters theorem

first there is a different between `log^2(n)` and `(log(n))^2` , because `(log(n))^2 = log(n) * log(n)` and `log^2(n) = log(log(n))` 

masters theorem used to solve reclusive problems

<img src="https://i.loli.net/2020/09/17/vbxPT2sZVXzU3nM.jpg" alt="Lightbox"  />

examples

```
T(n) = 3T(n/2) + n^2
a = 3 , b = 2 , k = 2 p=0
a < b^k
3 < 4
so it's the case 3)a so T(n) = O(n^2 * log^0(n))
```

```
T(n) = 4*T(n/2) + n^2
a=4 , b=2 , k=2 , p=0
4=2^2
so it's case 2)a T(n) = O(n^log(4) * log(n)) = O(n^2*log(n))
```

```
T(n) = T(n/2)+n^2
a=1 , b=2 , k=2 , p=0
1 < 2^2
it's case 3)a T(n) = O(n^2 * log^0(n)) = O(n^2)
```

```
T(n) = 2^n*T(n/2)+n^n master theoreme is not applied
```

```
T(n) = 16*T(n/4)+n
a = 16 b=4 k=1 p=0
16>4
so it's 1)
```

```
T(n) = 2*T(n/2)+n*log(n)
a=2 b=2 k=1 p=1
2=2 , p>-1 so it's 2)a
```
if it doesn't directly look like theorem we need to refactoring it
```
T(n) = 2*T(n/2)+n/log(n)
	 = 2T(n/2)+n*log^-1(n)
	 a=2 , b =2 , k=1 p=-1
	 s = 2^1 so it's case 2)b
```

```
T(n) = 2*T(n/4)+n^0.51
a=2 b=4 k=051 p=0
2 < 4^0.51
case 3)a
```

```
T(n) = 05*T(n/2)+1/n
a=0.5 not valid
```

```
T(n) = 6*T(n/3)+n^2*log(n)
a=6 b=3 k=2 p=1
6 < 3^2
so it's 3)a
```

```
T(n) = 64 T(n/8) - n^2 * log(n)
can not apply master theorem
```

```
T(n) = 7*T(n/3)+n^2
a=7 b=3 k=2 p=0
7 < 3^2
case 3)a
```

```
T(n) = 4*T(n/2)+log(n)
a=4 b=2 k=0 p=1
4 > 2^0
case 1
```

```
T(n) = sqrt(2)*T(n/2)+log(n)
a=sqrt(2) b=2 k=0 p=1
sqrt(2) > 2^0
case 1
```

```
T(n) = 2*T(n/2)+sqrt(n)
a=2 b=2 k=1/2 p=0
2>2^1/2
case 1
```

```
T(n) = 3*T(n/2)+n
a=3 b=2 k=1 p=0
3 > 2^1
case 1
```

```
T(n) = 3*T(n/3)+sqrt(n)
a=3 b=3 k=1/2 p=0
3>3^1/2
case 1
```

```
T(n) = 4*T(n/2)+C*n
a=4 b=2 k=1 p=0
4 > 2^1
case 3)b
```

```
T(n)=3*T(n/4)+(n*log(n))
a=3 b=4 k=1 p=1
3 < 4
case 3)a
```

### Analysis Space Complexity

same as time complexity we have space complexity for Iterative programs and recursive programs. Some times we sacrifice time for space.

```pseudocode
Algo(A,1,n)
{
	int i;
	for(i=1 to n) A[i] = 0;
}
```

this space complexity is constant `O(1)` because we don't take the initial input into count. So we calculate extra spaces such as `i`

```pseudocode
Algo(A,1,n)
{
	int i;
	create B[n];
	for(i=1 to n) B[i] = A[i];
}
```

the amount of space required is `O(n)` because we declare `B[n]` that contain `n` element. Same as Time complexity we didn't take in count the constants in other word we take higher degree.

```pseudocode
Algo(A,1,n)
{
	create B[n,n];
	int i,j;
	for(i=1 to n)
		for(j=1 to n) B[i,j]=A[i]
}
```

space complexity is `O(n^2)`

```pseudocode
A(n)
{
	if(n>=1)
	{
		A(n-1);
		pf(n);
	}
}
```

because the program is small we are going to use the tree method , take `n=3`

![image-20200919192742044](https://i.loli.net/2020/09/20/ZSGkWKiABa1whLb.png)

![image-20200919192808057](https://i.loli.net/2020/09/20/pLAGNsbQkIvH2Y1.png)

the output is `1 2 3` because every time I end call I print it

the space complexity is the number of stacks which is `O(kn)` where `k` is constant so we write it as `O(n)`

time complexity is `T(n) = T(n-1)+1` it's not form where we can apply master theorem so we gonna use back substitution

```
T(n)  =T(n-1)+1
T(n-1)=T(n-2)+1
T(n-2)=T(n-3)+1
T(n) = T(T(n-2)+1)+1
	 = T(n-2) +2
	 = (T(n-3)+1) +2
	 = T(n-3)+3
	 = T(n-k)+k
	 = T(n-n)+n
	 = T(0)+n
	 = 1+n
	 = O(n)
```

so time and space complexity is `O(n)`

```pseudocode
A(n)
{
	if(n>=1)
	{
		A(n-1);
		pf(n);
		A(n-1);
	}
}
```

number of recursive calls are

```
A(3) = 15 = 2^(3+1) - 1
A(2) =  7 = 2^(2+1) - 1
A(1) =  3 = 2^(1+1) - 1
A(n) = (2^n) - 1
```

this is not the space complexity because the stack will only need 4 cells `A(0),A(1),A(2),A(3)`  in the stack in order to compute it where the stack will start to empty it self every time it reach `A(0)`  , so it's `(n+1)*k` where `k` is the size occupied by one cell in stack so space complexity is nothing more than `O(nk) = O(n)`.

To optimize it We can use Dynamic programming which is to store the already computed values for not compute them again.

```pseudocode
A(n) -> T(n)
{
	if(n>=1)
	{
		A(n-1); -> T(n-1)
		pf(n); -> 1
		A(n-1); -> T(n-1)
	}
}
```

```
T(n) 	= 2*T(n-1)+1 ; n > 0
T(n-1)	= 2*T(n-2)+1
T(n-2)	= 2*T(n-3)+1

T(n) 	= 2(2T(n-2)+1)
         = 4T(n-2)+2+1
         = 4(2T(n-3)+1)+2+1
         = 8T(n-3)+7
         = 2^k * T(n-k) + 2^(k-1)+...+2^2+2+1
         = 2^n * T(0)+2^n-1 + 2^n-2 + ... + 2^2 + 2 + 1
         = 2^n + 2^n-1 + 2^n-2 + ... + 2^2 + 2 + 1
         = O(2^n+1) = O(2^n)
```

the time complexity is very big `O(2^n)` we can lower it with Dynamic Programming as we said.