O(1) constant time

입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘

F(int[] n){
	return (n[0] == 0) ? true:false;
}

O(n) linear time

입력 데이터의 크기에 비례해서 처리 시간이 걸리는 알고리즘

F(int[] n){
	for i=0 to n.length
    		print i
}

O(n²) quadratic time

예시)

F(int[] n){
	for i=0 to n.length
    		for j=0 to n.length
        		print i+j;
}

O(nm) quadratic time

F(int[] n,int[] m){
	for i=0 to n.length
    		for j=0 to m.length
        		print i+j;
}

O(n³) polynomial/cubic time

F(int[] n){
	for i=0 to n.length
    		for j=0 to n.length
        		for k=0 to n.length
        			print i+j+k;
}

O(2ⁿ) exponential time

Fibonacci numbers

F(n, r){
	if (n<=0) return 0;
    	else if (n==1) return r[n]=1;
    	return r[n] = F(n-1,r) + F(n-2,r)
}

O(log n)

binary search
한 번 처리가 진행될 때 마다 이후 검색 수가 절반씩으로 줄어드는 알고리즘

F(k,arr,s,e){
	if (s>e) 
    		return -1;
    	m= (s+e)/2;
        if(arr[m] == k)
        	return m;
        else if (arr[m] > k) 
        	return F(k,arr,s,m-1);
        else 
        	return F(k,arr,m+1,e);
}

Big-O 표기법

F(int[] n){
	for i=0 to n.length
    		print i
   	for i=0 to n.length
    		print i
}

n번 두 번 실행 --> 2n 이지만 Big-O 표기법에서는 과감히 상수 버리기
--> O(n)

출처:https://www.youtube.com/watch?v=6Iq5iMCVsXA