Linear Space: O(n)

Grokking Algorithm Complexity and Big-O

Ask Author

Back to course home

0% completed

Vote For New Content

Linear Space: O(n)

Table of Contents

Contents are not accessible

Linear Space Complexity $O(n)$ refers to algorithms where the memory usage grows linearly with the input size. This occurs when an algorithm needs to store a new copy of the input or requires auxiliary data structures proportional to the input size.

Key Characteristics

In an algorithm with $O(n)$ space complexity:

The memory usage increases linearly with the size of the input.
Common in tasks that duplicate the input data or process each element with additional storage.

Code Example 1: Copying a String

Let’s look at an example where we create a copy of a string. This requires memory proportional to the length of the string, resulting in $O(n)$ space complexity.

Python3

. . . .

Explanation:
- The copy_string method takes an input string s and creates a copy copied_str.
- Since copied_str is a complete duplicate of s, it requires memory proportional to the length of s, resulting in $O(n)$ space complexity.

Code Example 2: Copying an Array

Here’s another example that demonstrates $O(n)$ space complexity by creating a copy of an array.

Python3

. . . .

Explanation:
- This copy_array function takes an input array arr and creates a duplicate copied_arr.
- Since copied_arr contains each element of arr, it requires memory proportional to the size of arr, resulting in $O(n)$ space complexity.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible