Easiest way of solving algorithms

How to Analyze an Algorithm
I is initially 1
Analysis Piece of Code: 1x2 =2
For ( I= 1; I < n; I = I x 2) 2x2= 22
{ 22 x 2=23
Stmt; :::::::::::::::::::
How much
}
times???
Blindly, we can not say that the loop is repeating n times as each time I is 2K
multiply by 2. Assume that the loop is executing 2K times, loop condition
will terminate when I > = n since I = 2K
2K >= n => log2 2K >= log2n  K= log2n  f(n)= Θ(log2n)
Loop body statements will be executed Θ(log2n) times.


Analysis Piece of Code:
For ( I= 1; I < n; I=Ix2 For ( I= 0; I < n; I ++)
{ {
Smt; Stmt;
} }
I =2x2x2……….=n I=1+1+1……………..= n
1 is added up until I >=n. 1 is added up to k
2 is being multiplied until i.>=n times.
How much times 2 is being multiplied, let it be K=n
up to 2k times
2k = n  K=log2n




For ( I= 1; I < n; I = I x 2) n=8 n=10
{ I I
Stmt; 1 1
} 2 2
4 4
log2 n = log2 8= log2 23 = 3 times loop body will
8* 8
be executed. condition
false
log2 n = log2 10= 3.2 = 4 times 16* condition false

In this case, take ceil value of log2 n i.e log2 n