Space Complexity (Asymptotic Analysis)
Data Structures And Algorithms
In this lecture on asymptotic analysis, we learned about time complexity and space complexity. Time
complexity is the measure of the amount of time taken by an algorithm to execute as the input size
grows. Space complexity, on the other hand, is the measure of the amount of memory space required by
an algorithm to execute as the input size grows.
We learned that time complexity is commonly expressed using big O notation, and the most common
time complexities are O(1), O(n), O (log n), O (n log n), O(n^2), and O(2^n). We also looked at some
common loops, nested loops, and analyzed their time complexities.
In terms of space complexity, we learned that as long as the number of variables is constant, the space
complexity would remain constant as well. Auxiliary space refers to the extra space created that is not
related to input or output. Sorting algorithms like bubble sort, quicksort, and insertion sort have an
auxiliary space of θ(n).
Overall, understanding time and space complexity is crucial for analyzing and improving the
performance of algorithms.
here are some examples to illustrate space complexity and auxiliary space:
Example 1: Space complexity
Consider a function that takes an array of size n as input and creates a new array of size n^2 to perform
some computation. The space complexity of this function would be theta(n^2) because the amount of
memory required by the function grows quadratically with the input size.
Example 2: Auxiliary space
Consider a function that takes an array of size n as input and sorts it using bubble sort. Bubble sort is an
in-place sorting algorithm, which means it sorts the array by swapping elements within the same array
without creating a new one. However, bubble sort requires some extra memory to perform the swaps.
The amount of extra memory required by bubble sort is proportional to the size of the array, so the
auxiliary space complexity of the function would be theta(n).
Example 3: Space complexity vs. time complexity
Consider a function that takes an array of size n as input and computes the sum of all elements in the
array. One way to do this is to iterate over the array and add up all the elements. This approach has a
time complexity of theta(n) because it needs to visit each element once. However, the space complexity
of this function is only theta (1) because it only needs to store a single variable to keep track of the
running sum.
Data Structures And Algorithms
In this lecture on asymptotic analysis, we learned about time complexity and space complexity. Time
complexity is the measure of the amount of time taken by an algorithm to execute as the input size
grows. Space complexity, on the other hand, is the measure of the amount of memory space required by
an algorithm to execute as the input size grows.
We learned that time complexity is commonly expressed using big O notation, and the most common
time complexities are O(1), O(n), O (log n), O (n log n), O(n^2), and O(2^n). We also looked at some
common loops, nested loops, and analyzed their time complexities.
In terms of space complexity, we learned that as long as the number of variables is constant, the space
complexity would remain constant as well. Auxiliary space refers to the extra space created that is not
related to input or output. Sorting algorithms like bubble sort, quicksort, and insertion sort have an
auxiliary space of θ(n).
Overall, understanding time and space complexity is crucial for analyzing and improving the
performance of algorithms.
here are some examples to illustrate space complexity and auxiliary space:
Example 1: Space complexity
Consider a function that takes an array of size n as input and creates a new array of size n^2 to perform
some computation. The space complexity of this function would be theta(n^2) because the amount of
memory required by the function grows quadratically with the input size.
Example 2: Auxiliary space
Consider a function that takes an array of size n as input and sorts it using bubble sort. Bubble sort is an
in-place sorting algorithm, which means it sorts the array by swapping elements within the same array
without creating a new one. However, bubble sort requires some extra memory to perform the swaps.
The amount of extra memory required by bubble sort is proportional to the size of the array, so the
auxiliary space complexity of the function would be theta(n).
Example 3: Space complexity vs. time complexity
Consider a function that takes an array of size n as input and computes the sum of all elements in the
array. One way to do this is to iterate over the array and add up all the elements. This approach has a
time complexity of theta(n) because it needs to visit each element once. However, the space complexity
of this function is only theta (1) because it only needs to store a single variable to keep track of the
running sum.
