# 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**

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 Ω**

```
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 Θ**

```
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 :

```
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

```
A()
{
int i;
for(i = 1 to n) pf("text");
}
time complexity : O(n)
```

```
A()
{
int i;
for(i = 1 to n)
for(j = 1 to n)
pf("omar");
}
time complexity : O(n^2)
```

```
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))
*/
```

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

```
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)
*/
```

```
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)
*/
```

```
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
*/
```

```
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))
*/
```

```
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)
```

```
A()
{
// assume n >= 2
while(n>1)
{
n = n/2;
}
}
time complexity : O(log(n))
```

```
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))
*/
```

```
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

```
A(n)
{
if(...)
return A(n/2)+A(n/2);
}
T(n) = c+2*T(n/2)
```

```
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
```

```
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
```

### 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

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.

```
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`

```
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.

```
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)`

```
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`

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)`

```
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.

```
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.

## Discussion