Nested for loop
Pattern problems
sum of a pair whose sum is equal to k
=============================================

What is time complexity :

Manish :
The Time taken by computer to execute the program is called time complexity

I wrote a program of length 500 lines 

windows 8 gb i5 - 20 micro seconds
windows 16gb i7 - 10 micro seconds
Apple - 5 mili seconds
super computer  - 1 milli second

Actual Defnition
the rate at which time increase wrt to inputs it is time complexity

0=dy/dx= dt/dinput =this rate is constant across all the machines

for(int i=0;i<n;i++)
{
   system.out.println(x);
}
1. condition check
2. statement execution
3. incr/decr

5 -> 15+1= 16 steps == 0(16)=0(5*3+1) = 0(n*3+1)= 0(3n+1)~0(n)

computer scients measure time complexity in 3 ways

1 lakh + 1rupee ~ 1 lakh

big 0 notation
omega (X)
theata (X)
===================
distance - meters
liquid - liters
1 liter ~ 1 km
====================
ANSI - that measurement
======================
3 considerations for time complexity

1. always consider worst case time complexity
2. Avoid constants
3 . Avoid lower values

name=sc.next();
name= "Virat"
if(name == "Santosh")
 sop("Hi I am Santosh"
else if(name == "Vineerth)
  sop("Hi I am Vineeth"
else if(name == "Manish")
  sop("Hi I am Manish")
else
  sop("else user not found");

best time complexity is 0(2)
worst time complexity 0(8)

for(int i=0;i<n;i++)
{
   sop("Hi I am Santosh");
}
=======================================
0(1) == Best Time complexity
for(int i=0;i<0;i++)
{
  for(int i=0;i<0;i++)
  {
  }
}
==============================
I =0  time n
i=1 time n
i=2 timen

i=n time n

n+n+n+........................n
=n*n=0(n^2)
===================================

while()
{
}
is equivalent to for loop

i=0
while(i<n)
{
  for(int j=0;j<n;j++)
  {
     for(int k=0;k<n;k++)
     {
     }
  }
  i++;
}
==============================
it is order of 0(n^3)

n2 + n2 +.....

n*n^2=n^3=0(n^3)
========================================
Avg tc =best+worst/2

=======================

0(n^3+n+2) ~ 0(n^3)

0((1 lakh)^3 + 1 lakh +2) ~ 0(n^3)
============================

0(10^6+10000+2)

1 crore ~ 
0(1)
=============================
for(i=0;i<n;;i++)
{
  for(int j=0;j<n;j++)
  {
     for(int k=0;k<n;k++)
     {}
  }
}

for(int j=0;j<n;j++)
  {
     for(int k=0;k<n;k++)
     {}
  }

o(n^3+n^2) = 0(n^3)
===================
for(i=0;i<n;i++)
{
}

for(int i=0;i<n;i++)
{
  if else break continue
}

for(int i=0;i<n;i++)
{
  if 
}


0(n)+0(n)+0(n)= 3*0(n) = 0(n)

0(1),0(n), 0(n^2), 0(n^3)

0(log n) binary search
0(n logn) Merge sort , Quick sort