Time Complexity.


টাইম কমপ্লেক্সিটি হচ্ছে computational complexity . একটা algorithm রান হতে ঠিক কত টুকু সময় লাগে টাইম কমপ্লেক্সিটি সেটা বর্ণনা করে। এটাকে বিগ O দ্বারা প্রকাশ করা হয়। সাধারণত দুই ধরনের complexity কম্পিউটার বিজ্ঞানে আলোচনা করা হয়। 
১. Time Complexity 
২. Space Complexity .
Complexity বলতে সাধারণ Time Complexity বুঝায়।
একটা প্রোগ্রাম execution-এর সময় কখন টাইম লাগে।
১.Assignment Operation. ( a =7) Time Complexity O (1)
২.Comparison of Operation. (a >b ) Time Complexity O (1)
৩. Mathematical Operation. (a =3+9) Time Complexity O (1)
৪.Function Call Operation.
৫. Inside Of Function Operation.

public class timeComplexity {
    public static void main(String[] args) {
        int a,b,result;
        a=10;               //O(1)
        b=20;               //O(1)
        result=a+b;     //O(1)+O(1)
        System.out.println("This Program Time complexity O(1)");
    }
}

 উপরের প্রোগ্রামের টাইম কমপ্লেক্সিটি O (4) হওয়ার কথা কিন্তু  যখন কোন Programer অপারেশন সংখ্যা Input-এর উপর নির্ভর করে না সেই প্রোগ্রামের Complexity  হয় O (1).
আরেকটা উদাহরণ লক্ষ্য করি 

 public class timeComplexity {
    public static void main(String[] args) {
        Scanner sc;
        int n,result;
        sc = new Scanner(System.in);
        n=sc.nextInt();
        result=(n*(n+1))/2;
        System.out.println("This program Complexity also O(1)");
    }
}

 উপরের program টির Complexity O (১). যদি একই প্রোগ্রামটি আমরা এইভাবে লিখি 

 public class timeComplexity {
    public static void main(String[] args) {
        Scanner sc;
        int n,result=0,i;
        sc = new Scanner(System.in);
        n=sc.nextInt();
        for(i=1;i<=n;i++){
        result=result+1;  //O (1)+O (1)
    }
        System.out.println("This program Complexity also O(1)");
    }

}


এখানে for loop-এ n এর মানের উপর ভিত্তি করে operation সংখ্যা বাড়তেছে অর্থাৎ 
n =১ হলে operation সংখ্যা ২*১
n =২ হলে Operation সংখ্যা ২*২
n =৩ হলে Operation সংখ্যা ২*৩
এখানে complexity O (২n )=২O (n )=O (n )
২ constant হওয়ার কারণে ignore করা হয়েছে। Program টি Linear Complexity প্রদর্শন করে.
nested loop program.

 for(i=1;i<=n;i++){
            for(j=0;j<n;j++)

              count=count+1;

 n=1 হলে count=1
n=2 হলে count=4
n=3 হলে count=9
n=10 হলে count=100
n=100 হলে count=10000
অর্থাৎ কমপ্লেক্সিটি O (n^2) . যদি ৩ টি লুপ থাকে তখন কমপ্লেক্সিটি O(n^৩) .
input এর উপর নির্ভর করে time Complexity কম থেকে বেশি দেয়া হল । 
n ইনপুট হলে, time Complexity 
O(1)
O(log n) for binary search
O(√(n))
O(n)
O(n^2)
O(n^3)
O(n^n)
https://www.youtube.com/watch?v=bfB4YN_4Vyo&index=2&list=PLym69wpbTIIEOesltWGUsVnY9HDWbJit_