Algorithms Using C++ | Sorting, Searching, Recursion, Backtracking, Greedy, Dynamic Programming

This complete tutorial on Algorithms Using C++ explains time and space complexity analysis, sorting and searching algorithms, recursion, backtracking, greedy algorithms, and dynamic programming. Following best practices, it helps learners write efficient and optimized C++ programs for problem-solving and competitive programming.

Algorithms Using C++ – Complete Tutorial

1. Time and Space Complexity

Time Complexity

  1. Measures how fast an algorithm runs as input size grows
  2. Big O Notation examples:
  3. O(1) – Constant
  4. O(n) – Linear
  5. O(n²) – Quadratic
  6. O(log n) – Logarithmic

Space Complexity

  1. Measures extra memory used by an algorithm
  2. Includes recursion stack, auxiliary arrays, or hash tables

Example:


// Linear search O(n) time, O(1) space
int linearSearch(int arr[], int n, int key) {
for(int i=0; i<n; i++) if(arr[i]==key) return i;
return -1;
}

2. Sorting Algorithms

a) Bubble Sort – O(n²)


void bubbleSort(int arr[], int n) {
for(int i=0;i<n-1;i++)
for(int j=0;j<n-i-1;j++)
if(arr[j]>arr[j+1]) swap(arr[j],arr[j+1]);
}

b) Selection Sort – O(n²)

  1. Find min element and place at start

c) Insertion Sort – O(n²)

  1. Insert each element into sorted subarray

d) Merge Sort – O(n log n)

  1. Divide and conquer

#include <vector>
void mergeSort(vector<int>& arr, int l, int r);

e) Quick Sort – O(n log n) average

  1. Partition array around pivot

3. Searching Algorithms

a) Linear Search – O(n)

  1. Check each element sequentially

b) Binary Search – O(log n)

  1. Requires sorted array

int binarySearch(int arr[], int l, int r, int key) {
while(l<=r) {
int m = l + (r-l)/2;
if(arr[m]==key) return m;
if(arr[m]<key) l = m+1;
else r = m-1;
}
return -1;
}

4. Recursion

Recursion is when a function calls itself to solve a smaller problem.

Example: Factorial


int factorial(int n) {
if(n<=1) return 1;
return n * factorial(n-1);
}

Best Practices:

  1. Define base case
  2. Avoid deep recursion to prevent stack overflow

5. Backtracking

Backtracking is a trial-and-error approach to solve problems like N-Queens, Sudoku, maze solving.

Example: N-Queens


bool solve(int row, vector<int>& board);

Use Cases:

  1. Puzzle solving
  2. Constraint satisfaction problems

6. Greedy Algorithms

Greedy algorithms make locally optimal choices at each step to find global optimum.

Example: Coin Change (Greedy)


vector<int> coins = {25,10,5,1};
int amount = 63;

Use Cases:

  1. Minimum spanning tree (Prim, Kruskal)
  2. Huffman encoding

7. Dynamic Programming (DP)

DP solves problems by storing intermediate results (memoization/tabulation) to avoid recomputation.

Example: Fibonacci using DP


int fib(int n) {
vector<int> dp(n+1,0);
dp[1] = 1;
for(int i=2;i<=n;i++) dp[i] = dp[i-1]+dp[i-2];
return dp[n];
}

Best Practices:

  1. Identify overlapping subproblems
  2. Decide between top-down (memoization) or bottom-up (tabulation)

Best Practices

  1. Analyze time and space complexity before implementation
  2. Prefer efficient algorithms for large input
  3. Use STL functions (sort, lower_bound, upper_bound) for fast implementation
  4. Modularize code for recursive, greedy, or DP solutions
  5. Test algorithms on edge cases

Common Mistakes

  1. Ignoring base case in recursion
  2. Using greedy where DP is required
  3. Forgetting to sort for binary search
  4. Not considering time/space constraints for large inputs

Summary

In this chapter, you learned about Algorithms Using C++, including:

  1. Time and space complexity analysis
  2. Sorting and searching algorithms
  3. Recursion, backtracking
  4. Greedy algorithms
  5. Dynamic programming

Mastering algorithms is essential for efficient problem-solving, competitive programming, and real-world software development.