Time Complexity

25 September 2025 10:18

Time Complexity:

➢ Performance is the most important thing for any software.

➢ There are two categories of performance.

○ Performance
▪ Speed Of Execution
▪ Memory Consumption

Memory Consumption:

➢ The amount of memory consumed in RAM, whenever we run the program is known as Memory Consumption.
➢ Whenever we are designing a program, we should make sure that our application will consume less memory during execution.
➢ This measure we call it as Space Complexity.

Space Complexity:

➢ The amount of extra memory used by the application for the execution is called Space Complexity.
➢ Whenever we want to increase the performance of our application, the execution memory should consumed less.

Speed Of Execution:

➢ How fast an application runs on a system is known as Speed of Execution.

➢ This is one of the most important factors in improving the performance of an application.
➢ Speed of execution depends on many factors like internet speed, hardware configuration, good server, etc.
➢ We cannot say speed of execution is the same as time complexity, because execution speed varies across different systems.
➢ Time Complexity is calculated based on the algorithm or logic, independent of the system.

Time Complexity:

➢ The measure of the performance of an algorithm is known as Time Complexity.

➢ It is measured based on how the algorithm’s execution time grows with respect to the input size.
➢ Time complexity is calculated on the number of steps (operations) taken by the logic to complete the execution.

Example:
public static void main(String[] args) {
int a = 10, b = 20;
int res = a+b;
[Link](res);
}

➢ Here, the time complexity is calculated based on the logic of the program, irrespective of the system environment.

Q) What is the time complexity of the above Program?

➢ Assume that each statement will take 1 unit of time (unit can be anything, 1 millisecond, 1 nanosecond, 1 microsecond,… based
on the system architecture).
➢ 1unit means not one second, millisecond,… it’s a constant time irrespective of values.
➢ Then we have 3 statements in the above program. So the time taken to execute the above program is 3 units.

Irrespective of the values of a and b, this program always takes the same number of steps (about 3 operations). It does not depend on
the input values, so the execution time is constant.

Performance Analogy:

➢ In algorithms, we usually consider 3 cases:

1) Best Case (Ω – Omega): The minimum time an algorithm takes to run.
2) Average Case (Θ – Theta): The expected/typical time an algorithm takes to run.
3) Worst Case (O – Big O): The maximum time an algorithm can take to run.
➢ Each case is represented using a different symbol.
➢ In practice, we don’t focus much on Best and Average cases. Because if an algorithm works well in the Worst Case, it will
automatically work well in the Best and Average cases too.

Example:

public static int binarySearch(int[] arr, int n) {

int left = 0, right = [Link] - 1;
while (left < right) {
int mid = (left + right) / 2;

New Section 1 Page 1

 int mid = (left + right) / 2;
if (arr[mid] == n) return mid;
if (arr[mid] < n) left = mid;
if (arr[mid] > n) right = mid;
}
return -1;
}
➢ Here, time complexity of binarySearch is

Best Case (Ω)

• Element is found at the first middle element checked.
• Time Complexity: Ω(1) → only 1 comparison needed.

Average Case (Θ)

• Element is somewhere in the array; on average, we halve the search range log₂ n times.
• Time Complexity: Θ(log n)

Worst Case (O)

• Element is at an end of the array or not present; we keep halving until only 1 element remains.
• Time Complexity: O(log n)

Time Complexity:

➢ Time complexity of an algorithm specifies how the number of basic operations grows as the size of the input increases.

Types of Time Complexities:

Time Complexity type Representation in Worst Case Example

Constant O(1) Accessing an array element,
push/pop in stack
Linear O(n) Traversing an array/linked list
Logarithmic O(log n) Binary Search
Linearithmic O(n log n) Merge Sort, Quick Sort
Quadratic O(n²) Bubble Sort, Insertion Sort
(worst)
Exponential O(2ⁿ) Recursive Fibonacci, Subset
generation
Factorial O(n!) Generating all permutations

Constant Time Complexity: O(1)

Example-1:
public static void addTwoNumbers(int a, int b) {
int sum = a + b;
[Link]("Sum: " + sum);
}

Example-2:
public static void printFirstElement(int[] arr) {
if([Link] > 0)
[Link]("First element: " + arr[0]);
}

Linear Time Complexity: O(n)

Example-1:
public static void printArray(int[] arr) {
[Link]("Array elements: ");
for(int i : arr) [Link](i + " ");
[Link]();
}

Example-2:
public static void sumNumbers(int n) {
int sum = 0;
for(int i = 1; i <= n; i++) sum += i;
[Link]("Sum of 1 to " + n + ": " + sum);
}

New Section 1 Page 2

 }

Logarithmic Time Complexity: O(log n)

Example-1:
public static void divideUntilOne(int n) {
int count = 0;
while(n > 1) {
n /= 2;
count++;
}
[Link]("Divisions by 2 until 1: " + count);
}

Example-2:
public static void multiplyUntilN(int n) {
int power = 1;
int count = 0;
while(power < n) {
power *= 2;
count++;
}
[Link]("Multiplying by 2 until >= " + n + ": " + count + " steps");
}

Example-3:
public static void printPowersOfTwo(int n) {
int i = 1;
[Link]("Powers of 2 less than " + n + ": ");
while(i < n) {
[Link](i + " ");
i *= 2;
}
[Link]();
}

Linearithmic Time Complexity: O(n log n)

Example-1:
public static void repeatedDoublingPrint(int[] arr) {
[Link]("Repeated doubling: ");
for(int i=0;i<[Link];i++) {
int x = 1;
while(x < [Link]) {
[Link](arr[i] + " ");
x *= 2;
}
}
[Link]();
}

Example-2:
public static void countDoublingSteps(int n) {
int count = 0;
for(int i=1;i<=n;i++) {
int j = 1;
while(j <= n) {
count++;
j *= 2;
}
}
[Link]("Count of doubling steps: " + count);
}

Example-3:
public static void countArrayDoubling(int[] arr) {
int count = 0;
for(int i=0;i<[Link];i++) {
int j = 1;
while(j <= [Link]) {
count++;
j *= 2;
}
}

New Section 1 Page 3

 }
[Link]("Count of array doubling: " + count);
}

Quadratic Time Complexity: O(n²)

Example:
public static void printAllPairs(int n) {
[Link]("All pairs from 1 to " + n + ":");
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
[Link]("(" + i + "," + j + ")");
}

Exponential Time Complexity: O(2ⁿ)

Example:
public static void recursiveCalls(int n) {
if(n == 0) return;
[Link]("Call with n = " + n);
recursiveCalls(n-1);
recursiveCalls(n-1);
}

Fractional Time Complexity: O(n!)

Example:
public static void generatePermutations(String str, String ans) {
if([Link]() == 0) [Link](ans);
for(int i=0;i<[Link]();i++)
generatePermutations([Link](0,i)+[Link](i+1), ans+[Link](i));
}

New Section 1 Page 4