Time complexity measures how the runtime of an algorithm grows as the input size increases. Space complexity measures how much extra memory an algorithm needs while running.

• Describes how the number of operations changes with input size n.
• Written using Big O notation: O(1), O(n), O(n2), etc.
• Use the fastest-growing term and ignore constants.

This function always does the same work no matter how large the array is.

#include <iostream>
using namespace std;
 
int getFirst(int arr[], int n)
{
    return arr[0];
}
 
int main()
{
    int arr[] = {10, 20, 30};
    cout << getFirst(arr, 3) << endl;
    return 0;
}

• Time complexity: O(1)
• Explanation: Single access, independent of n.

This function checks every element once.

#include <iostream>
using namespace std;
 
bool contains(int arr[], int n, int target)
{
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == target)
            return true;
    }
    return false;
}
 
int main()
{
    int arr[] = {4, 7, 1, 9};
    cout << contains(arr, 4, 9) << endl;
    return 0;
}

• Time complexity: O(n)
• Explanation: Work grows in direct proportion to input size.

This function compares every pair of elements.

#include <iostream>
using namespace std;
 
void printPairs(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << arr[i] << "," << arr[j] << endl;
        }
    }
}
 
int main()
{
    int arr[] = {1, 2, 3};
    printPairs(arr, 3);
    return 0;
}

• Time complexity: O(n2)
• Explanation: Two nested loops cause quadratic growth.

Search by splitting the input in half each step.

#include <iostream>
using namespace std;
 
bool binarySearch(int arr[], int n, int target)
{
    int left = 0;
    int right = n - 1;
 
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
            return true;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
 
    return false;
}
 
int main()
{
    int arr[] = {1, 3, 5, 7, 9};
    cout << binarySearch(arr, 5, 7) << endl;
    return 0;
}

• Time complexity: O(log n)
• Explanation: Input size halves each step.

Many efficient sorting algorithms run in O(n log n) time.

#include <algorithm>
#include <iostream>
using namespace std;
 
int main()
{
    int arr[] = {5, 2, 8, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    sort(arr, arr + n);
 
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

• Time complexity: O(n log n)
• Explanation: Sorting splits work and processes each part.

• Best case: the fastest possible input for the algorithm.
• Average case: expected performance for a typical input.
• Worst case: the slowest possible input.

• Best case: O(1) when the target is at the first position.
• Worst case: O(n) when the target is missing or at the end.

• Best case: O(n) if the array is already sorted and the algorithm checks for no swaps.
• Worst case: O(n2) when the array is in reverse order.

• Best case: O(1) if the middle element is the target.
• Worst case: O(log n) if the target is not found.

• Average case: O(n log n)
• Worst case: O(n2) when the pivot is always the smallest or largest element.

• Measures extra memory used by the algorithm.
• Focuses on additional data structures or recursion stack.
• Ignore the space used by the input itself.

This function uses only a few variables.

#include <iostream>
using namespace std;
 
int sumFirstTwo(int arr[], int n)
{
    int sum = arr[0] + arr[1];
    return sum;
}
 
int main()
{
    int arr[] = {5, 6, 7};
    cout << sumFirstTwo(arr, 3) << endl;
    return 0;
}

• Space complexity: O(1)
• Explanation: Only a fixed number of extra variables are used.

This function creates a new array of size n.

#include <iostream>
using namespace std;
 
int* copyArray(int arr[], int n)
{
    int* copy = new int[n];
    for (int i = 0; i < n; i++)
    {
        copy[i] = arr[i];
    }
    return copy;
}
 
int main()
{
    int arr[] = {2, 4, 6};
    int* copy = copyArray(arr, 3);
    cout << copy[0] << " " << copy[1] << " " << copy[2] << endl;
    delete[] copy;
    return 0;
}

• Space complexity: O(n)
• Explanation: Extra memory grows with input size.

Recursive functions use stack memory for each call.

#include <iostream>
using namespace std;
 
int factorial(int n)
{
    if (n == 0)
        return 1;
    return n * factorial(n - 1);
}
 
int main()
{
    cout << factorial(5) << endl;
    return 0;
}

• Space complexity: O(n)
• Explanation: Recursion adds one stack frame per call.

• O(1): single access or fixed operations.
• O(log n): divide-and-conquer (binary search).
• O(n): single loop over input.
• O(n log n): efficient sorting algorithms.
• O(n2): nested loops over input.

From best to worst, use this ordering when comparing growth rates:

1. O(1) - constant time
2. O(log n) - logarithmic time
3. O(n) - linear time
4. O(n log n) - linearithmic time
5. O(n2) - quadratic time
6. O(n3) - cubic time
7. O(2n) - exponential time
8. O(n!) - factorial time

Smaller growth means better performance as input size increases.

• Choose the algorithm with lower growth for large n.
• If two algorithms have the same Big O, compare constant factors and memory use.
• For small inputs, readability and simplicity also matter.

• Ignore constant multipliers: O(2n) becomes O(n).
• Ignore lower-order terms: O(n + n2) becomes O(n2).
• Count loops, recursion depth, and extra data structures.