Time Complexity

What is Time Complexity ?

Time Complexity measures how the running time of an algorithm / Program increases as the
input size (n) increases.
 It does NOT measure actual seconds.
 It counts number of basic operations.

Why Time Complexity is needed ?

 To compare algorithms .
 To predict performance for large inputs.
 To select the most efficient algorithm.
Asymptotic Notations :
Asymptotic notations describe the growth rate of an algorithm.

1. Big O Notation — O(f(n))

Meaning: Upper bound (Worst-case performance) : Tells maximum time an algorithm can take.

Definition:
An algorithm is O(f(n)) if its running time does not exceed f(n) for large n.

Example:
public class Main {
public static void main(String[] args) { Real-Life Example:
int n = 5; // example value
 Searching a name in an unsorted list
for (int i = 0; i < n; i++) {
[Link]("Hello");
 Worst case → name is at last position
} O(n)
}
}  Big O notation represents the worst-case time
complexity of an algorithm.
 Loop runs n times
 Time Complexity = O(n)
2. Big Theta — Θ(f(n))

Meaning:
Exact bound : Algorithm always takes same order of time

Definition:
An algorithm is Θ(f(n)) if it has both upper and lower bounds equal to f(n).

Example:

for (int i = 0; i < n; i++) {

[Link]("Hello");
}

 Always runs n times

 Best = Worst = Average = n
 Time Complexity = Θ(n)

 Big Theta gives the tight bound / average of an algorithm.

3. Big Omega — Ω(f(n))

Meaning: Lower bound (Best-case performance)

Definition: An algorithm is Ω(f(n)) if it takes at least f(n) time.

Example: Linear Search:

 Best case → element found at first position

 Time = Ω(1)

 Big Omega represents the best-case time complexity.

Summary Table

Notation Case Meaning

Big O (O) Worst Maximum time

Big Theta (Θ) Average / Exact Tight bound

Big Omega (Ω) Best Minimum time

Analysis Techniques

1. Worst-Case Analysis

Maximum time taken : Most commonly used in real applications.

Example: Linear Search in array:

Case Time
Element at end O(n)

 Worst-case analysis gives the maximum possible running time.

2. Best-Case Analysis

Minimum time taken

Example: Linear Search:

Case Time
Element at first position O(1)

 Best-case analysis gives the minimum running time.

3. Average-Case Analysis

Average time over all inputs

More difficult to compute.

Example: Linear Search:

 On average → element found in middle
 Time = O(n/2) ≈ O(n)

Average-case analysis calculates expected performance over all inputs.

Common Time Complexities
Examples
Growth Order of Notations (Small to Large) :
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

1) O(1) — Constant Time

Example:
[Link]("Hello");

•Time does not depend on n

2) O(log n) — Logarithmic Time

Example: Binary Search
 Divide problem by 2 each step

3) O(n) — Linear Time

Example: Single loop

for (int i = 0; i < n; i++)

4) O(n log n)
Example:
 Merge Sort
 Quick Sort (average case)

5) O(n²) — Quadratic Time

Example: Nested loops

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)

6) O(2ⁿ) — Exponential Time

Example:
Recursive Fibonacci
7) O(n!) — Factorial Time
Example:
Traveling Salesman (Brute force)

Final Summary :

 Big O → Worst-case
 Big Theta → Exact bound
 Big Omega → Best-case
 Worst-case is most important
 Ignore constants & lower terms
 Used to compare algorithms
PROGRAMS
1) Constant Time Complexity (O(1))
public class Main {

public static int getFirstElement(int[] arr, int size) {

return arr[0];
}

public static void main(String[] args) {

int[] arr = {10, 20, 30, 40};
[Link]("First element: " + getFirstElement(arr, 4));
}
}
PROGRAM 2: Cubic Time Complexity (O(n³))

public class Main {

public static void findTriplets(int[] arr, int size) {
for (int i = 0; i < size - 2; i++) {
for (int j = i + 1; j < size - 1; j++) {
for (int k = j + 1; k < size; k++) {
if (arr[i] + arr[j] + arr[k] == 0) {
[Link]("Triplet found: "
+ arr[i] + ", " + arr[j] + ", " + arr[k]);
}
}
}
}
} Output:
public static void main(String[] args) { Triplet found: 0, -1, 1
int[] arr = {0, -1, 2, -3, 1}; Triplet found: 2, -3, 1
int size = [Link];

findTriplets(arr, size);
}
}
PROGRAM 3: Linear Time complexity: O(n)

public class Main {

public static void main(String[] args) {
public static void reverseArray(int[] arr, int size) {
int[] arr = {1, 2, 3, 4, 5};
int left = 0;
int size = [Link];
int right = size - 1;
reverseArray(arr, size);
while (left < right) {
// swap
[Link]("Reversed array: ");
int temp = arr[left];
for (int i = 0; i < size; i++) {
arr[left] = arr[right];
[Link](arr[i] + " ");
arr[right] = temp;
}
}
left++;
}
right--;
}
}
Output:
Reversed array: 5 4 3 2 1
 PROGRAM 4: O(n2)
public static void main(String[] args) {
public class Main { int[] arr = {5, 2, 9, 1, 5, 6};
int size = [Link];
public static void insertionSort(int[] arr, int size) {
for (int i = 1; i < size; i++) { insertionSort(arr, size);
int key = arr[i];
int j = i - 1; [Link]("Sorted array: ");
for (int i = 0; i < size; i++) {
while (j >= 0 && arr[j] > key) { [Link](arr[i] + " ");
arr[j + 1] = arr[j]; }
j--; }
} }
arr[j + 1] = key;
}
Output:
} Sorted array: 1 2 5 5 6 9

The time complexity for the Insertion Sort code is O(n²) in the worst and average cases,
and O(n) in the best case.
Space Complexity
What is space complexity?
Space complexity = Total memory required by an algorithm to run.
It includes:
1. Fixed part → constants, program instructions, primitive variables.
2. Variable part → input data, dynamic memory, recursion stack, auxiliary space.

It is not just the size of the file on your hard drive; it is the dynamic memory required while the code is
actually running. It is calculated using the following formula:

{Total Space Complexity} = {Input Space} + {Auxiliary Space}

•Input Space: The memory required to store the input data (e.g., the array of books you are sorting).
•Auxiliary Space: The extra or temporary memory used by the algorithm to solve the problem (e.g., the
temporary arrays leftArr and rightArr created in your Merge Sort code).2
Why it is needed ?
Understanding space complexity is vital for several real-world reasons:
 Hardware Constraints: Many devices, like smartwatches, medical implants, or IoT sensors, have very
limited RAM (sometimes only a few KB). An algorithm with high space complexity might crash these
devices.
 Scalability: An algorithm that works for 10 items might use O(n^2) space. If you suddenly give it
1,000,000 items, the memory requirement grows exponentially, leading to a "Memory Limit Exceeded"
error.
 Cost Efficiency: In cloud computing (like AWS or Azure), you pay for the memory you use. Efficient
code reduces the operational cost of running large-scale applications.

 Prevention of Crashes (Stack Overflow): As seen in your recursion example, every recursive call
takes up Stack Space. If the space complexity is too high (too many recursive calls), the program will
crash with a Stack Overflow.
Auxiliary Space Complexity
Extra memory used by an algorithm apart from input data.
 If an algorithm uses temporary variables/arrays/structures, that’s auxiliary space.
 Input itself is not counted.

Example 1 – In-place algorithm (O(1) auxiliary space)

public class Main {
// Reversing array in-place
public static void reverseArray(int[] arr, int n) {
int start = 0, end = n - 1;
while (start < end) {
// swap
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
 start++;
end--;
}
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int n = [Link];
reverseArray(arr, n);
[Link]("Reversed array: ");
for (int i = 0; i < n; i++) {
[Link](arr[i] + " "); Output:
Reversed array: 5 4 3 2 1
}
}
}
No extra memory (just a few variables) ⇒ O(1) auxiliary space
Example 2 – Uses extra memory (O(n) auxiliary space)
public static void main(String[] args) {
// Reversing array using extra array int[] arr = {1, 2, 3, 4, 5};
int n = [Link];
public class Main {
reverseArray(arr, n);
public static void reverseArray(int[] arr, int n) {
int[] temp = new int[n]; // extra array [Link]("Reversed array: ");
for (int i = 0; i < n; i++) {
// fill temp with reversed elements [Link](arr[i] + " ");
for (int i = 0; i < n; i++) { }
temp[i] = arr[n - i - 1]; }
} }

// copy back to original array

for (int i = 0; i < n; i++) {
arr[i] = temp[i];
}
}

Needs another array ⇒ O(n) auxiliary space

Real-Time Comparison
Imagine you want to create a list of numbers from 1 to N.

Approach A: Fixed Space (O(1) Auxiliary Space)

This approach just prints numbers. It doesn't store them, so it uses almost no extra memory
regardless of how big N is.
public class Main {

public static void printNumbers(int n) {

for (int i = 1; i <= n; i++) {
[Link](i + " "); // uses only one variable 'i'
}
}
Output (for n = 10):
public static void main(String[] args) {
int n = 10; // example 1 2 3 4 5 6 7 8 9 10
printNumbers(n);
}
}
Approach B: Linear Space (O(N) Auxiliary Space)

This approach stores all numbers in a vector first. If N is a billion, your computer might run out of
RAM.
import [Link];

public class Main {

public static ArrayList<Integer> storeNumbers(int n) {

ArrayList<Integer> v = new ArrayList<>();

for (int i = 1; i <= n; i++) {

[Link](i); // similar to push_back
}

return v;
}

public static void main(String[] args) {

int n = 10; // example
ArrayList<Integer> result = storeNumbers(n); Output:Stored numbers: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[Link]("Stored numbers: " + result);
}
}
Stack vs. Heap in Space Complexity public class Main {
Stack Space vs Heap Space
public static int factorial(int n) {
a) Stack Space if (n == 0)
return 1;
 Memory allocated automatically (compile-time).
 Used for: return n * factorial(n - 1); // recursive call
}
o Local variables
public static void main(String[] args) {
o Function calls int n = 5;
o Recursion (function call stack)
int result = factorial(n);
 Limited size (causes stack overflow if too deep recursion). [Link]("Factorial of " + n + " is: " + result);
}
Example – Recursion uses stack space
}
Each recursive call consumes stack memory.
factorial(5) → 5 stack frames.
factorial(100000) → Stack Overflow!
b) Heap Space
 Memory allocated dynamically (runtime). public class Main {
 Used for:
public static void main(String[] args) {
o Large arrays int[] arr = new int[1000000]; // allocated on heap
o Objects created with new or malloc //in Java
 Must be manually managed (delete in C++, free in C).
arr[0] = 42;
Example – Heap allocation [Link](arr[0]);
#include <iostream>
// No need to manually delete memory
using namespace std;
// Java uses Garbage Collection
}
Heap can store large data (bigger than stack). }
But forgetting delete ⇒ memory leak.
 Stack Space: Typically used for Local Variables and Function Calls. It is small and fast. If you use
deep recursion, you exhaust this space.

 Heap Space: Used for Dynamic Allocation (like new in C++ or malloc in C). It is much larger but
requires careful management to avoid memory leaks.
 Comparison – Stack vs Heap
Feature Stack Heap
Automatic (compiler Manual (programmer
Allocation
manages) manages)
Function scope (ends on Until delete or program
Lifetime
return) ends
Size Limited (MBs) Large (GBs)
Speed Fast (contiguous memory) Slower (fragmentation)
Use case Recursion, local vars Dynamic arrays, big objects
Memory Leak /
Error Stack Overflow
Fragmentation
Summary
 Auxiliary space = extra memory (not input).
 Stack space = recursion, local vars (small, fast, limited).
 Heap space = dynamic memory (large, manual, slower).