O(N)

for (int i = 0; i < N; i++)
{
  std::cout << i << std::endl;
}

for (int i = 0; i < N; i++)
{
  std::cout << i << std::endl;
}

The loop runs from i = 0 to i = N - 1, which means it executes N iterations in total. Since the work done inside the loop (std::cout << i) is a constant-time operation, the overall time complexity grows linearly with N, i.e., O(N).

O(N²)

for (int i = 0; i < N; i++)
{
  for(int k = 0; k < Y; k++)
  {
    std::cout << i * k << std::endl;
  }
}

for (int i = 0; i < N; i++)
{
  for(int k = 0; k < Y; k++)
  {
    std::cout << i * k << std::endl;
  }
}

The outer loop runs N times, and for each iteration, the inner loop runs Y times. This results in N × Y iterations in total. Since the body of the loop executes in constant time, the overall time complexity is O(N·Y). If Y scales proportionally with N, this simplifies to O(N²).

O(N³)

for (int i = 0; i < N; i++)
{
  for(int k = 0; k < Y; k++)
  {
    for (int j = 0; j < E; j++)
      std::cout << i * k << std::endl;
  }
}

for (int i = 0; i < N; i++)
{
  for(int k = 0; k < Y; k++)
  {
    for (int j = 0; j < E; j++)
      std::cout << i * k << std::endl;
  }
}

Basically it’s same with O(N²), we just add one more inner loop that rus E times. So the overall time complexity is O(N·Y·E). If the Y and E scales proportionally with N, this simplifies to O(N³)

O(logN)

int binarySearch(int arr[], int N, int target) {
    int left = 0, right = N - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1; // not found
}

int binarySearch(int arr[], int N, int target) {
    int left = 0, right = N - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1; // not found
}

This algorithm runs in O(log N) time because the search space is divided in half at each step. On every iteration, either the left or the right half of the array is eliminated, reducing the problem size by a factor of two. As a result, the number of steps required grows logarithmically with the size of the input array.

O(NlogN)

void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    // merging step
    std::vector<int> temp;
    int i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (arr[i] < arr[j]) temp.push_back(arr[i++]);
        else temp.push_back(arr[j++]);
    }
    while (i <= mid) temp.push_back(arr[i++]);
    while (j <= right) temp.push_back(arr[j++]);
    for (int k = 0; k < temp.size(); k++) {
        arr[left + k] = temp[k];
    }
}

void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    // merging step
    std::vector<int> temp;
    int i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (arr[i] < arr[j]) temp.push_back(arr[i++]);
        else temp.push_back(arr[j++]);
    }
    while (i <= mid) temp.push_back(arr[i++]);
    while (j <= right) temp.push_back(arr[j++]);
    for (int k = 0; k < temp.size(); k++) {
        arr[left + k] = temp[k];
    }
}

Merge Sort runs in O(N log N) time. The array is repeatedly divided into halves, which takes log N levels of recursion. At each level, the merging step processes all N elements in linear time. Combining these two factors, the total time complexity is O(N log N).

Ford–Johnson (Merge-Insertion Sort)

The Ford–Johnson algorithm, also known as merge-insertion sort, has a worst-case time complexity of O(N log N). Its main contribution is that it minimizes the number of comparisons required for sorting, making it nearly optimal for small input sizes. However, due to its complexity and overhead, it is rarely used in practice compared to simpler algorithms like Quick Sort or Merge Sort.