Array

Grokking Algorithm Complexity and Big-O

Ask Author

Back to course home

0% completed

Vote For New Content

Array

Table of Contents

Contents are not accessible

Arrays are fundamental data structures that store elements in contiguous memory locations. They are essential for organizing data and enabling efficient access.

In this section, we will explore two types of arrays:

Static arrays
Dynamic arrays.

1. Static Arrays

Static arrays have a fixed size, determined when the array is created. The size cannot be changed during the program's execution.

Key Characteristics:

Memory Allocation: Allocated in contiguous memory blocks.
Fixed Size: The size is set during initialization and cannot be modified.

Python3

. . . .

Time Complexity Analysis

Access: $O(1)$ , as we can access array elements using its index.
Linear Search: $O(n)$ – Each element may need to be checked to find a value.
Binary Search: $O(\log n)$ – For sorted arrays, halves the search space each step.
Sorting: $O(n \log n)$ – Efficient sorting algorithms (like merge sort) take $O(n \log n)$ time.

Space Complexity Analysis

Space Complexity: $O(n)$ , where n is the number of elements in the array.
Auxiliary Space: $O(1)$ since no additional space is used other than the array itself.

2. Dynamic Arrays

Dynamic arrays, unlike static arrays, grow in size as new elements are added. They start with an initial capacity, and when this capacity is exceeded, the array resizes—typically doubling its size. This resizing process involves copying all existing elements into a new, larger array.

Creating Dynamic Arrays in Different Languages

Dynamic arrays are handled differently across programming languages. Here’s how to create them in popular languages:

Language	Dynamic Array Type	Initialization
Python	`list`	`arr = []`
Java	`ArrayList`	`ArrayList<Integer> arr = new ArrayList<>();`
JavaScript	`Array`	`let arr = [];`
C++	`std::vector`	`std::vector<int> arr;`
C#	`List<T>`	`List<int> arr = new List<int>();`
Go	`slice`	`arr := []int{}`

Key Characteristics

Resizable: Automatically resizes when the capacity is reached.
Amortized Time Complexity:
- Append Operation: $O(1)$ on average, but $O(n)$ during resizing.
Memory Allocation:
- When resizing occurs, a new array double the size of the original is created, and existing elements are copied over.

Python3

. . . .

Time Complexity Analysis

Access by Index: $O(1)$ – Direct access to elements by index is constant time.
Insertion at the End: Average $O(1)$ , Worst $O(n)$ – Appending is usually quick, but resizing may require $O(n)$ .
Insertion at the Beginning or Middle: $O(n)$ – Elements need shifting to make space.
Deletion at the End: $O(1)$ – Removing the last element doesn’t require shifting.
Deletion at the Beginning or Middle: $O(n)$ – Elements shift to fill the gap after deletion.
Linear Search: $O(n)$ – Each element may need to be checked to find a value.
Binary Search: $O(\log n)$ – For sorted arrays, halves the search space each step.
Sorting: $O(n \log n)$ – Efficient sorting algorithms (like merge sort) take $O(n \log n)$ time.

Space Complexity Analysis

Auxiliary Space for Resizing:
- When a dynamic array reaches its capacity, it doubles in size, leading to a temporary overhead of $O(n)$ during the copy operation.

Arrays are efficient for accessing elements by index but can be costly for insertions and deletions in the middle. Dynamic arrays add flexibility by resizing automatically, but resizing operations are more memory-intensive. Different programming languages provide built-in data structures to handle dynamic arrays efficiently, allowing developers to manage growing data seamlessly.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible