Omar

Posted on

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