Analysing Algorithm (TC & SC)

Apriori Analysis:

• It is a determination of order of magnitude of a statement.

Ex:04

main()
{
  x = a+b;
  y = c+d;
  e = f+g;
  g = e+y;
  h = x+c;
}

Ex:05

main()
{
  x = y+z;
  for(i=1;i<=n;i++)
    x = y+z;
  for(i=1;i<=n;i++)
  {
    for(j=1;j<=n/2;j++)
    {
      x = y+z;
    }
  }
}

Ex:06

main()
{
  i = 1;
  while(i<=n)
  {
    x = y+z;
    i=i+1;
  }
}

Ex:07

main()
{
  i = 1;
  while(i<=n)
  {
    i = i+1;
  }
}

Ex:07

main()
{
  i = 1;
  while(i<=n)
  {
    i = i+5;
  }
}

Ex:08

main()
{
  i = 1;
  while(i<=n)
  {
    i = i+5;
    i = i+7;
    i = i+100;
  }
}

Ex:09

main()
{
  i = n;
  while(i>=1)
  {
    i = i-1;
  }
}

Ex:09

main()
{
  i = n;
  while(i>=1)
  {
    i = i-100;
  }
}

Ex:10

main()
{
  i = n;
  while(i>=1)
  {
    i = i-5;
    i = i-7;
    i = i-100;
  }
}

Ex:11

main()
{
  i = n;
  while(i>=1)
  {
    i = i-50;
    i = i-25;
    i = i-30;
  }
}

Ex:11

main()
{
  i = n;
  while(i>=1)
  {
    i = i-50;
    i = i-25;
    i = i-30;
    i = i+40;
  }
}

Ex:12

main()
{
  i = n;
  while(i>=1)
  {
    i = i-7;
    i = i+9;
    i = i-50;
    i = i+60;
  }
}

• NOTE
  • "I promise, before writing any program, I will first write its algorithm. I will follow this practice for every program from today onward."

Ex:13

main()
{
  i = 1;
  while(i<=n)
  {
    i = i+7;
    i = i+9;
    i = i+25;
  }
}

Ex:14

main()
{
  i = 1;
  while(i<=n)
  {
    i = i+10;
    i = i+20;
    i = i+30;
  }
}

Ex:15

main()
{
  i = 1;
  while(i<=n)
  {
    i = 2*i;
  }
}

Ex:16

main()
{
  i = 1;
  while(i<=n)
  {
    i = 3*i;
  }
}

Note:

• i = 1*i => log₁ n
• i = 2*i => log₂ n
• i = 3*i => log₃ n
• i = 4*i => log₄ n
• i = 10*i => log₁₀ n
• i = 100*i => log₁₀₀ n

Ex:17

main()
{
  i = 1;
  while(i<=n)
  {
    i = 2*i;
    i = 3*i;
  }
}

Ex:17A

main()
{
  i = 1;
  while(i<=n)
  {
    i = 2*i;
    i = 3*i;
    i = 4*i;
  }
}

Ex:18

main()
{
  i = n;
  while(i>1)
  {
    i = i/2;
  }
}

Ex:19

main()
{
  i = n;
  while(i>1)
  {
    i = i/2;
    i = i/3;
  }
}

Ex:19A

main()
{
  i = n;
  while(i>1)
  {
    i = i/5;
    i = i/7;
    i = i/2;
    i = i/3;
  }
}

Note:

• i = 1/i => log₁ n
• i = 2/i => log₂ n
• i = 3/i => log₃ n
• i = 4/i => log₄ n
• i = 10/i => log₁₀ n
• i = 100/i => log₁₀₀ n

Ex:20

main()
{
  i = n;
  while(i>1)
  {
    i = i/5;
    i = i/7;
    i = i/2;
    i = i/2;
    i = 4*i;
  }
}

Ex:21

main()
{
  i = n;
  while(i>75){
    i = i/2;
    i = i/7;
  }
}

Ex:22

main()
{
  i = 270;
  while(i<n){
    i = 2*i;
    i = 3*i;
    i = 4*i;
  }
}

Ex:23

main()
{
  i= 2;
  while(i<n)
  {
    i = i^2;
  }
}

NONE

• i = 200;
• i+2 = 202 => n/2;
• i-2 = 198 => n/2;
• i*2 = 400 => log₂ n
• i/2 = 100 => log₂ n
• i^2 = 40000 => log₂ (log₂ n)
• i^1/2 = 100 => log₂ (log₂ n)

Ex:24

main()
{
  i= 25;
  while(i<n)
  {
    i = i^3;
  }
}

Ex:25

main()
{
  i= n;
  while(i>2)
  {
    i = i^1/2;
  }
}

Ex:26

main()
{
  i = n;
  while(i>64)
  {
    i = i^1/51;
  }
}

Ex:27

main()
{
  i = 25;
  while(i<n)
  {
    i = i^31;
    i = i^2;
    i = i^3;
  }
}

Ex:28

main()
{
  i = 64;
  while(i<n)
  {
    i = i^1/2;
    i = i^1/3;
  }
}

Ex:29

main()
{
  i = 10;
  while(i<=n)
  {
    i = i + 7;
    i = i * 10;
    i = i ^ 9;
  }
}