Time complexity

Time complexity

is a measure used in computer science to analyze the efficiency of an algorithm. It describes the amount of time an algorithm takes to run as a function of the input size. Time complexity is typically expressed using Big O notation,

Big O

which provides an upper bound on the growth rate of the algorithm's running time relative to the input size. The Big O notation helps in classifying algorithms based on their efficiency.

Here are some commonly used time complexity notations:

O(1)

constant complexity, 입력값이 증가해도 시간은 늘지 않음.

def sum(n):
	return n*(n+1)//2

O(N)

linear complexity, 입력값이 증가함에 따라 시간 또한 "같은비율"로 증가

def search(arr, n, k):
	for i in arr:
		if i == k:
			return True
	return False

O(log N)

logarithmic complexity, Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.

def binary_search(arr, n, k): #반반씩 쪼개기
    low, high = 0, n-1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == k:
            return True
        if arr[mid] > k:
            high = mid - 1
        else:
            low = mid + 1
    return False

O(n^2) - Quadratic time complexity. The algorithm's running time grows quadratically with the input size. For example, nested loops iterating over a 2D array.

O(2^n) - Exponential time complexity. The algorithm's running time grows exponentially with the input size. Typically seen in algorithms with exhaustive search or recursion.

To be continued..