Grokking Algorithm Complexity and Big-O
Ask Author
Back to course home

0% completed

Vote For New Content
Linear Space: O(n)
On this page

Key Characteristics

Code Example 1: Copying a String

Code Example 2: Copying an Array

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
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
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!

On this page

Key Characteristics

Code Example 1: Copying a String

Code Example 2: Copying an Array