You can also find all 30 answers here 👉 Devinterview.io - Big-O Notation
Big O notation serves as a standardized measure for algorithmic performance, focusing on time and space complexity. It's crucial for comparing algorithms and understanding their scalability.
-
Dominant Term: The notation simplifies complexity expressions to their most significant terms, making them easier to compare.
-
Asymptotic Analysis: Big O emphasizes how algorithms perform as data scales, offering a high-level understanding of efficiency.
-
Worst-Case Performance: Big O provides an upper limit on resources needed, offering a conservative estimate for the most challenging scenarios.
.jpeg?alt=media&token=fbb27d2b-31bf-4456-8f93-f4b62b0e5344)
-
Constant Complexity
$O(1)$ - Resources used are independent of the input size.
- Time Example: Arithmetic operations, Array index access
- Space Example: Using a fixed-size array
-
Logarithmic Complexity
$O(\log n)$ - Resource usage grows logarithmically with input size.
- Time Example: Binary search in a sorted array
- Space Example: Binary tree traversal
-
Linear Complexity
$O(n)$ - Resource usage scales linearly with input size.
- Time Example: Element search in an unordered list
- Space Example: Allocating an array proportional to input size
-
Linearithmic Complexity
$O(n\log n)$ - Resource usage grows at a rate between linear and quadratic. Often seen when combining linear and logarithmic operations.
- Time Example: Efficient sorting algorithms like merge sort and quicksort
- Space Example: Divide-and-conquer algorithms that decompose the problem
-
Quadratic Complexity
$O(n^2)$ - Resources scale with the square of the input size.
- Time Example: Algorithms with simple nested loops, e.g., bubble sort
- Space Example: Creating a two-dimensional matrix based on input size
-
Exponential Complexity
$O(2^n)$ - Resource usage doubles (or increases exponentially) with each additional unit of input.
- Time Example: Generating all subsets of a set
- Space Example: Recursive algorithms that double the size of the call stack for each input element
- Resource Management: It helps in pre-allocating sufficient resources, especially in constrained environments.
- Reliability: Provides a performance guarantee, crucial in time-sensitive tasks.
- Optimization: Aids in identifying bottlenecks and areas for potential improvement, ensuring the algorithm is as efficient as possible.
Here is the Python code:
def linear_search(arr, target):
for i, num in enumerate(arr):
if num == target:
return i
return -1-
Worst-Case: The target is not in the list, resulting in
$O(n)$ time complexity. -
Best-Case: The target is the first element, with
$O(1)$ time complexity. -
Average-Case: Simplifies to
$O(n)$ as every element has an equal chance of being the target.
Let's discuss the meanings and practical applications of three important notations:
Big-O defines the worst-case scenario of an algorithm's performance. It gives an upper limit, denoted as
In simpler terms, if an algorithm has a time complexity of
Big-Theta represents the exact growth rate, showing both an upper and lower limit for a function. It is denoted as
An algorithm with a time complexity of, say,
Big-Omega provides the best-case time complexity, giving a lower limit for the function's growth rate. It is denoted as
If an algorithm's best-case time complexity is
An algorithm requiring a specific time-bound to be effective might be suitably described using Big-Theta notation. Conversely, algorithms designed for different use cases, such as adaptive sorting algorithms, are better depicted with Big-Omega and Big-Oh notations.
Understanding the role of constants and lower-order terms in Big-O analysis helps to differentiate between performance that's good in practice versus good in theory. Evaluation of these factors leads to the most accurate Big-O classification for an algorithm, providing practical insights into its efficiency.
Constants are numerical multipliers in functions that represent an exact number of operations an algorithm performs. However, in the context of Big-O analysis, they are not typically included as they do not affect the overall order of magnitude.
For example, an algorithm might have a runtime of
Lower-order terms, also referred to as "small-oh", correspond to the lower-graded factors in a given Big-O function and provide a more detailed view of the algorithm's behavior.
When dealing with multiple terms:
- The dominant term is retained for Big-O representation as it is the most influential for larger inputs.
- Lower-order terms and constants are omitted for the same reason.
For example, if an algorithm has a complexity of
Let's explore how amortized analysis can lead to more balanced complexity measures by considering the following algorithms:
This data structure combines the benefits of an array's fast random access with dynamic resizing. While single insertions might occasionally trigger expensive resizing, most insertions are quicker. Through amortized analysis, the average cost per operation is
Here is the Python code:
import ctypes
class DynamicArray:
def __init__(self):
self.n = 0 # Not the actual size
self.array = self.make_array(1)
def insert(self, elem):
if self.n == len(self.array):
self._resize(2 * len(self.array))
self.array[self.n] = elem
self.n += 1
def _resize(self, new_capacity):
new_array = self.make_array(new_capacity)
for i in range(self.n):
new_array[i] = self.array[i]
self.array = new_array
def make_array(self, cap):
return (cap * ctypes.py_object)()Despite its primarily logarithmic time complexity, there are situations where Binary Search can exceed this efficiency through repeated operations that halve the search range. With amortized analysis, such "good" or "lucky" scenarios are considered, leading to a balanced time complexity measure of
Here is the Python code:
def binary_search(arr, x):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
lo = mid + 1
else:
hi = mid - 1
return -1Standard Fibonacci calculations exhibit
Let's use Python:
def fibonacci(n, memo={}):
if n in memo:
return memo[n]
if n <= 2:
return 1
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]5. Describe how the coefficients of higher-order terms affect Big-O Notation in practical scenarios.
Although the dominant term typically defines a function's time complexity, coefficients of higher-order terms are not necessarily moot. Their impact can be tangible, especially in real-world applications.
Let's consider a scenario where we need to compare time complexities based on Big-O notation.
-
Low Order, Large Coefficient:
$3n + 500$ vs$6n + 10$ where$n$ is small:- Big-O suggests
$O(n)$ - In practice,
3ntends to outperform6n, especially for diminutiven.
- Big-O suggests
-
Low Order, Small Coefficient:
$0.05n + 3$ vs$0.1n + 1.5$ where$n$ is large:- Big-O suggests
$O(n)$ - With sizeable
n, the constant factors can still have an observable cumulative effect.
- Big-O suggests
-
High Order, Small Coefficient:
$0.00001n^2 + 10$ vs$0.0001n^2 + 1$ :- Big-O suggests
$O(n^2)$ - For large
$n$ , the leading term becomes so dominant that the impact of the coefficients is relegated.
- Big-O suggests
-
High Order, Large Coefficient:
$10n^2 + 5n + 2$ vs$2n^2 + 3n + 1$ for all$n$ :- Big-O suggests
$O(n^2)$ - Coefficients can modify performance marginally, but not enough to alter the asymptotic behavior.
- Big-O suggests
Many algorithms exhibit these characteristics.
- Linear-time algorithms are often referred to as
$O(n)$ even though they can be$4n + 2$ as a worst-case scenario. However, for large datasets, the difference between$4n$ and$0.5n$ can be substantial, as opposed to the theoretical constant factor of 4.
6. Explain how probabilistic algorithms can have a different Big-O Notation compared to deterministic ones.
In this scenario, let's discuss the problems for which probabilistic algorithms can provide approximate solutions in expected polynomial time, even though a deterministic algorithm might require exponential time.
The goal is to find out whether a graph
The standard "Breadth-First Search" or "Depth-First Search" algorithms requires linear time in
The "Randomized Incremental Algorithm" emulates a different strategy. It initially considers the graph to be disconnected and then adds edges one by one, checking for graph connectivity after each addition. This approach, on average, operates in expected constant time before the graph becomes connected and
The
- The first stage, where the graph is disconnected, expects a constant time operation (usually ends prematurely).
- The second stage, activated with a probability smaller than
$(2/3)^{3 \sqrt{ 2 n} }$ , which can be bounded above by a constant$c$ , dictates an$O(c|V|)$ complexity.
Hence, in expected polynomial time,
Let's look at common array operations and their Big O-time complexities.
Accessing an array element by its index is a constant-time operation.
For an unsorted array, searching for a specific value might have a worst-case time complexity of
For a sorted array, binary search can be implemented, reducing the complexity to
Inserting an element at a specific index might require elements after that index to be 'shifted' to the next index. This shifting operation, especially in an array list, is a linear-time process.
Appending an element (insertion at the end) can generally be done in amortized constant time, unless the array needs to be resized, in which case it becomes a linear-time operation.
Deleting an element at a specific index will likely require subsequent elements to be shifted, which is a linear-time operation.
If you delete the last element, it's a *constant-time operation.
-
Sort: Many popular sorting algorithms
$e.g., quicksort, mergesort$ have an average and worst-case time complexity of$O(n \log n)$ . -
Transpose: Rearranging elements or swapping adjacent elements, such as in the "transpose" operation, is a constant-time process.
-
Merge in a Sorted Order: If both arrays are sorted into progressively larger or smaller elements, then it is possible — for many algorithms — to "merge" the two arrays into one array still sorted in a time linear to the total number of elements (remember, sorting entire datasets usually is a
$O(n \log n)$ operation).
Remember, these complexities are general. The actual performance can be influenced by the hardware and specific programming language. By knowing these complexities, you can better understand and predict the efficiency of your code.
While Linked Lists offer
That means, in the worst case, they could occupy as much space as an
-
Singly Linked List: Each node has a single pointer, typically 4-8 bytes on a 64-bit system, in addition to the data. Hence,
$O(1)$ pointers per node makes it$O(n)$ in terms of space. -
Doubly Linked List: Every node has two pointers, requiring either 8-16 bytes. While it's still
$O(1)$ in terms of pointers, it does have comparatively higher overhead than a singly linked list. -
Circularly Linked List: Similar to singly and doubly linked lists, but the tail node points back to the head. It doesn't impact the space complexity.
-
XOR Linked List: Uses bitwise XOR operations to store only one reference (as opposed to two in doubly linked lists). However, it's quite complex to implement and maintain, so it's used mainly for educational or theoretical purposes.
-
Auxiliary Pointer Singly Linked and Doubly Linked Lists: These lists have an additional pointer, increasing the per-node memory requirements and thus the space complexity.
Let's look at the Big-O complexities of various fundamental sorting algorithms.
Complexity:
- Best Case:
$O(n)$ when the list is already sorted due to the flag$swapped$ . - Worst Case:
$O(n^2)$ when each element requires$n-1$ comparisons and there are$n$ elements.
Complexity:
- Best Case:
$O(n^2)$ because$n-1$ passes are still made to find the largest element. - Worst Case:
$O(n^2)$ for the same reason.
Complexity:
- Best Case:
$O(n)$ when the list is already sorted. - Worst Case:
$O(n^2)$ occurs when the list is sorted in reverse order.$n-1$ comparisons and assignments are made for each of the$n$ elements.
Complexity:
- Best Case:
$O(n \log n)$ as it partitions the list equally and takes$n \log n$ time to merge. - Worst Case:
$O(n \log n)$ due to the same reasons.
Complexity:
- Best Case:
$O(n \log n)$ when the chosen pivot divides the list evenly all the time. - Worst Case:
$O(n^2)$ when the pivot is always one of the smallest or largest elements. This is more likely if the list is already partially sorted.
Complexity:
- Best Case:
$O(n \log n)$ - The heapify operation takes$O(n)$ time and the heap operations take$O(\log n)$ time. - Worst Case:
$O(n \log n)$ for the same reason.
Complexity:
- Best Case:
$O(n+k)$ for$k$ distinct elements with$O(n)$ time complexity. - Worst Case:
$O(n+k)$ for$k$ distinct elements.
Complexity:
- Best Case:
$O(nk)$ where$k$ is the number of digits in the maximum number. Actual complexity is$O(dn+k)$ . - Worst Case:
$O(nk)$ similar to the best case, but it varies based on the distribution of data.
Complexity:
- Best Case:
$O(n+k)$ where$k$ is the number of buckets or partitions. It can be made$O(n)$ when$k=n^2$ . - Worst Case:
$O(n^2)$ when all elements fall into a single bucket.
Complexity:
- Best Case: Depends on the gap sequence, but typically
$O(n \log n)$ . - Worst Case:
$O(n (\log n)^2)$ typically but can vary based on the gap sequence.
Binary Search is a Divide and Conquer algorithm primarily used on sorted lists to efficiently locate an element. It offers a time complexity of
-
Notable Efficiency: Binary Search outperforms linear search, which has a time complexity of
$O(n)$ , especially on longer lists. - Recursive or Iterative Implementation: The algorithm can be implemented using a recursive or an iterative approach.
- Memory Constraint: Binary Search navigates a list in memory without needing additional data structures, making it ideal for large datasets with limited memory resources.
Binary Search's time complexity is evaluated using a recurrence relation, benefiting from the Master Theorem:
where:
-
$T(n)$ is the time complexity. - The constant work done within each recursive call is
$1$ . - The algorithm divides the list into sublists of length
$\frac{n}{2}$ .
Here is the Pseudocode:
Let min = 0 and max = n-1
While min <= max
Perform middle calculation
If arr[middle] = target
: target found, return middle
If arr[middle] < target
: Discard the left sublist (set min = middle + 1)
Else
: Discard the right sublist (set max = middle - 1)
Return "not found"
-
Loop Control: Although not always true, the loop's primary control generally checks
min <= max. Each iteration, therefore, helps to halve the size of the sublist under consideration. -
Iteration Count: The number of iterations, in the worst-case, typically determines how efficiently Binary Search can reduce the search space. Also, the overall complexity can be expressed as:
The last term ranges up to
"Binary Search" employs an in-place approach. It navigates the input list without needing any auxiliary structures, demonstrating a space complexity of
Let's discuss the time and space complexities associated with basic Hash Table operations.
-
Search (Find Element) -
$O(1)$ - The hash function identifies the location of an element within the unique hash table.
-
Insert (Add New Element) -
$O(1)$ - The hash function determines placement, usually in constant time.
-
Delete (Remove Element) -
$O(1)$ - Similar to "Insert", this step generally requires only constant time.
-
Resize (Rehash for Dynamic Tables) -
$O(n)$ - Regarding amortized time, resizing arrays takes linear time but happens infrequently. Thus, the average time is amortized over many operations.
-
Rehash (during Resizing) -
$O(n)$ - Re-inserting all elements happens linearly with the number of items in the table.
In an ideal setting, each key is mapped to a unique hash, and thus a unique table slot. When dealing with collisions (two keys hashing to the same slot), some algorithms outshine others.
The time it takes to resolve a collision is crucial in forming the table's amortized bounds. Techniques include separate chaining and open addressing.
- Worst-Case Time:
$O(n)$ (All keys collide) - Amortized Time:
$O(1)$ - Worst-Case Space:
$O(n)$
Binary Search Trees (BST) are efficient for both search and insert operations, with average time complexity of
-
Search (Best & Worst):
$O(\log n)$ Best case: Root of the tree is the target. Each level eliminates half of the remaining nodes. Worst case: Tree is a single linked list. -
Insert:
$O(\log n)$ . Ensures the tree remains balanced.
Here is the Python code:
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return rootAVL Trees maximize search efficiency by remaining balanced. They guarantee worst-case time complexities of
-
Single Rotation: Utilized when an imbalance arises due to operations on either the left or right subtree of a node.
- Left Rotation: Resolves a
left-heavysituation. - Right Rotation: Resolves a
right-heavysituation.
- Left Rotation: Resolves a
-
Double Rotation: Employed when a node's imbalance is due to operations stemming from both subtrees.
- Left-Right (or Right-Left) Rotation: Applies both a left and a right (or vice versa) rotation to restore balance.
Here is the visual representation:
Before Rotation:
A(-2)
/
B(0)
\
C(0)
After rotation:
B(0)
/ \
C(0) A(0)
Here is the Python code for AVL Tree:
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
self.height = 1
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
root.height = 1 + max(get_height(root.left), get_height(root.right))
balance = get_balance(root)
if balance > 1 and value < root.left.value:
return right_rotate(root)
if balance < -1 and value > root.right.value:
return left_rotate(root)
if balance > 1 and value > root.left.value:
root.left = left_rotate(root.left)
return right_rotate(root)
if balance < -1 and value < root.right.value:
root.right = right_rotate(root.right)
return left_rotate(root)
return root
def get_height(node):
return node.height if node else 0
def get_balance(node):
return get_height(node.left) - get_height(node.right)
def right_rotate(z):
y = z.left
t3 = y.right
y.right = z
z.left = t3
z.height = 1 + max(get_height(z.left), get_height(z.right))
y.height = 1 + max(get_height(y.left), get_height(y.right))
return y
def left_rotate(z):
y = z.right
t2 = y.left
y.left = z
z.right = t2
z.height = 1 + max(get_height(z.left), get_height(z.right))
y.height = 1 + max(get_height(y.left), get_height(y.right))
return y13. Analyze the Big-O complexity of graph algorithms, including traversal and shortest path algorithms.
Graph algorithms vary in their computational requirements. The time complexity is often measured in Big O notation.
Here is the detailed breakdown:
-
Time Complexity:
$O(V + E)$ - Visiting all vertices and edges once. -
Space Complexity:
$O(V)$ - Underlying stack depth.
-
Time Complexity:
$O(V + E)$ - Visiting all vertices and edges once. -
Space Complexity:
$O(V)$ - Queue typically contains all vertices.
-
Time Complexity:
$O((V + E) \log V)$ - Efficient in practice on sparse graphs. -
Space Complexity:
$O(V)$ - Using a priority queue.
-
Time Complexity:
$O(VE)$ - Slower but robust, suitable for graphs with negative edges or cycles. -
Space Complexity:
$O(V)$ - Single-source shortest path tree. -
Negative Cycle Detection:
$O(V \cdot E)$
-
Time Complexity:
$O(V^3)$ - Finds all-pairs shortest paths. -
Space Complexity:
$O(V^2)$ - Dynamic Programming formulation
-
Time Complexity:
$O(\log V)$ on average - Admissible and consistent heuristics guide the search. Failing to do so can lead to higher time complexities. - Efficiency in practice often relies on a good heuristic function
$h(n)$ .
-
Time Complexity:
$O(VE + V^2 \log V)$ - Combines Bellman-Ford and Dijkstra's algorithms with the help of potential functions, making it particularly efficient for sparse graphs.
Heaps are specialized trees that enable fast operations such as insertions, deletions, and min/max lookups. They are widely used in priority queues and sort algorithms. Heaps come in two varieties: the min-heap, where the smallest key is at the root, and the max-heap, which places the largest key at the root.
-
Index:
$i$
nodes:$\left\lfloor \frac{i-1}{2} \right\rfloor$ parent,$2i+1$ left child,$2i+2$ right child -
Parent, Left Child, Right Child:
- Parent:
$\text{index} = \left\lfloor \frac{\text{index} -1}{2} \right\rfloor$ - Left Child:
$\text{index} = 2 \times \text{index} + 1$ - Right Child:
$\text{index} = 2 \times \text{index} + 2$
- Parent:
-
Insertion:
$O(\log n)$
The element to be inserted is placed at the leaf level, and then "heapified" (moved up).-
Time: This involves up to
$\log n$ swaps to restore the heap's structure. -
Space: The operation may incur up to
$O(\log n)$ space due to its iterative nature.
-
-
Deletion:
$O(\log n)$
The root element is replaced with the last node, and then "heapified" (moved down).-
Time: This includes up to
$\log n$ swaps to preserve the heap property. -
Space: It requires
$O(1)$ space, as it performs in-place swaps.
-
-
Min/Max Lookups:
$O(1)$
The smallest or largest element, respectively, can be found at the root.-
Time: This is a direct and constant time operation.
-
Space: It does not utilize additional space.
-
-
Extract Min/Max:
$O(\log n)$
Same as Deletion.-
Time: Like deletion, the process may take up to
$\log n$ swaps. -
Space: It requires
$O(1)$ space, as it performs in-place swaps.
-
Here is the Python code:
import heapq
# Create a min-heap
min_heap = []
heapq.heapify(min_heap)
# Insert elements:
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
# Delete/ Extract Min
print(heapq.heappop(min_heap)) # Output: 1
# Min/Max Lookup
print(min_heap[0]) # Output: 3 (the only remaining element)
# Create a max-heap
max_heap = []
heapq._heapify_max(max_heap)
# Insert elements into max-heap
heapq._heappush_max(max_heap, 3)
heapq._heappush_max(max_heap, 1)
# Delete/ Extract Max
print(heapq._heappop_max(max_heap)) # Output: 3Time-space tradeoffs characterize algorithms that can be optimized for either time or space, but generally not both.
- Time: Using a simple algorithm for compression or decompression can save computing time.
- Space: More sophisticated compression techniques can require additional space but reduce memory's overall size.
- Time: A more in-depth indexing mechanism can speed up word lookups to improve search time.
- Space: It consumes extra memory to store the index.
- Time: Persisting indices on disk rather than recreating them frequently can improve query time.
- Space: Requires storage on disk.
Here is the Python code:
# Simple compression algorithm (time optimized)
simple_compress = lambda data: ''.join(bin(ord(char))[2:].zfill(8) for char in data)
# Huffman compression algorithm (space optimized)
from heapq import heappop, heappush, heapify
def huffman_compress(data):
freq = {}
for char in data:
freq[char] = freq.get(char, 0) + 1
heap = [[f, [char, ""]] for char, f in freq.items()]
heapify(heap)
while len(heap) > 1:
lo = heappop(heap)
hi = heappop(heap)
for pair in lo[1:]:
pair[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
codes = dict(heappop(heap)[1:])
return ''.join(codes[char] for char in data), codesExplore all 30 answers here 👉 Devinterview.io - Big-O Notation