I. INTRODUCTION
Algorithmic efficiency is a cornerstone of computer science, and Big O notation provides a standardized language to describe how an algorithm's runtime or space requirements grow with the size of its input. Understanding Big O is critical for writing scalable and performant software, allowing developers to choose the most appropriate algorithm for a given problem. In recent years, Large Language Models, or LLMs, have demonstrated remarkable capabilities in understanding, generating, and transforming human language and code. These advanced AI systems have become indispensable tools for many developers, assisting with tasks ranging from code completion to debugging. This article delves into the intriguing question of whether these powerful LLMs can reliably analyze code and accurately determine the Big O complexity of algorithms. We will explore their strengths, expose their inherent limitations, and discuss how they can best serve as assistants in this complex analytical task.
II. THE ESSENCE OF BIG O NOTATION
Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. In the context of algorithms, it is used to classify algorithms according to how their running time or space requirements grow as the input size grows. It specifically focuses on the worst-case scenario, providing an upper bound on the growth rate. For instance, an algorithm with O(N) complexity means its performance scales linearly with the input size N, while O(N^2) indicates a quadratic growth. Other common complexities include O(1) for constant time, O(log N) for logarithmic time, and O(N log N) for "linearithmic" time.
The derivation of Big O complexity involves identifying the dominant term in the function that describes the algorithm's operations. Constant factors and lower-order terms are ignored because, as the input size N becomes very large, the highest-order term overwhelmingly dictates the growth rate. For example, an algorithm performing 5N + 10 operations would be classified as O(N) because the 5 and 10 become insignificant compared to N when N is sufficiently large. Consider a simple Python function that iterates through a list to count its elements.
CODE SNIPPET: Simple Linear Iteration
def count_elements(items):
"""
Counts the number of elements in a list.
This is a simple example to illustrate O(N) complexity.
"""
count = 0
# The loop below iterates once for each item in the 'items' list.
# If 'items' has 'N' elements, this loop runs 'N' times.
for item in items:
count += 1 # This operation takes constant time.
return count
In the `count_elements` function, the `for` loop executes exactly N times, where N is the number of elements in the `items` list. Inside the loop, the `count += 1` operation takes a constant amount of time. Therefore, the total time complexity is directly proportional to N, which is expressed as O(N). This fundamental understanding of how operations scale with input size is what an LLM would ideally need to emulate.
III. LLMS AND THEIR CODE UNDERSTANDING CAPABILITIES
Large Language Models are sophisticated neural networks trained on vast datasets of text and code, learning patterns, grammar, and semantic relationships. When processing code, LLMs tokenize it into smaller units, then use attention mechanisms to understand the relationships between these tokens, effectively building a statistical representation of the code's structure and meaning. This process allows them to perform impressive feats such as generating syntactically correct code, translating between programming languages, identifying potential bugs, and explaining complex code segments.
Their strengths lie in their ability to recognize common programming constructs, understand variable scopes (within their context window), and infer intent from function names and comments. They can often provide coherent explanations of what a piece of code does, suggest improvements, or even refactor it. However, LLMs do not "execute" code in the traditional sense; they operate based on statistical probabilities derived from their training data. They predict the most likely sequence of tokens given an input, rather than simulating the runtime behavior of a program. This fundamental difference introduces significant limitations when it comes to tasks requiring deep algorithmic reasoning.
IV. CAN LLMS DETERMINE BIG O COMPLEXITY RELIABLY
The question of whether LLMs can reliably determine Big O complexity is nuanced, with arguments supporting limited capabilities countered by significant challenges.
SUBSECTION: THE ARGUMENT FOR LIMITED CAPABILITY
LLMs can, to a certain extent, infer algorithmic complexity due to their extensive training on codebases that often include documented algorithms and their associated complexities. They excel at pattern recognition, which is a key component of initial complexity analysis. For example, an LLM can easily identify a single `for` loop iterating N times and associate it with O(N) complexity. Similarly, nested `for` loops are a strong indicator of O(N^2) or higher polynomial complexity. They can also recognize common recursive patterns, such as those found in binary search (O(log N)) or merge sort (O(N log N)), if these patterns were sufficiently represented in their training data alongside their complexities.
Furthermore, LLMs can leverage syntactic analysis to understand the control flow structures, such as conditional statements, loops, and function calls. They can also glean semantic clues from variable names, function names, and inline comments, which often explicitly state the algorithm's purpose or even its expected complexity. For instance, a function named `bubble_sort` immediately suggests a known complexity. Consider the following implementation of Bubble Sort:
CODE SNIPPET: Bubble Sort (for pattern recognition)
def bubble_sort(arr):
"""
Implements the Bubble Sort algorithm.
Known for its O(N^2) worst-case and average-case time complexity.
Space complexity is O(1) as it sorts in-place.
"""
n = len(arr)
# Outer loop for passes, runs N times.
for i in range(n):
# Inner loop for comparisons and swaps, runs approximately N-i-1 times.
# The total number of comparisons is roughly (N-1) + (N-2) + ... + 1,
# which sums to N * (N-1) / 2, indicating N^2 growth.
for j in range(0, n - i - 1):
# Compare adjacent elements and swap if they are in the wrong order.
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
An LLM observing this code would likely identify the nested `for` loops, each iterating up to `n` times, leading to a strong inference of O(N^2) complexity. This capability is largely based on statistical correlation and pattern matching rather than a deep, first-principles understanding.
SUBSECTION: THE CRITICAL LIMITATIONS AND CHALLENGES
Despite their pattern-matching prowess, LLMs face significant hurdles in reliably determining Big O complexity, primarily because they lack a true execution environment. They cannot run the code, trace its execution path, or simulate its behavior with various inputs. This leads to several critical limitations.
Firstly, Big O complexity often depends on the input data characteristics, distinguishing between best-case, average-case, and worst-case scenarios. Without executing the code or having a sophisticated symbolic execution engine, an LLM struggles to reason about all possible input distributions and their impact on control flow. For example, QuickSort has an average complexity of O(N log N) but a worst-case of O(N^2), a distinction that is difficult for an LLM to make without explicit information or deep statistical reasoning about pivot selection.
Secondly, algorithms with dynamic behavior, such as those employing memoization, dynamic programming, or complex recursive calls with overlapping subproblems, pose a significant challenge. The actual number of operations in these cases depends on the state of auxiliary data structures or the results of previous computations, which an LLM cannot track without execution. Similarly, amortized analysis, which describes the average performance of a sequence of operations over time (e.g., dynamic arrays), requires understanding state changes across multiple calls, a concept beyond the current capabilities of LLMs.
Thirdly, LLMs treat external library calls as opaque functions. If an algorithm relies on a function from an external library or a system call, the LLM cannot "look inside" that function to determine its complexity unless that information was explicitly present in its training data or documentation. It would either have to guess, assume constant time, or state its inability to determine the complexity.
Fourthly, LLMs are prone to "hallucinations," confidently generating incorrect answers if the patterns are ambiguous, if their training data was insufficient for a specific scenario, or if the problem requires genuine logical deduction rather than pattern recall. This unreliability makes them unsuitable for critical complexity analysis without human oversight.
Finally, the context window limitations of LLMs can hinder the analysis of complex algorithms spread across multiple functions or files. If the entire relevant code cannot fit within the model's input window, the LLM will have an incomplete view, leading to potentially inaccurate or partial complexity assessments.
V. HOW LLMS CAN SERVE AS VALUABLE ASSISTANTS
While LLMs cannot autonomously and reliably determine Big O complexity in all scenarios, they can serve as exceptionally valuable assistants in the process. Their capabilities can significantly augment a human developer's workflow.
One way they assist is by generating initial complexity hypotheses. Given a piece of code, an LLM can quickly suggest a preliminary Big O estimate based on common patterns, providing a starting point for deeper human analysis. They are also adept at identifying common algorithmic patterns, such as sorting algorithms, search algorithms, or graph traversals, which often have well-known complexities. This can help developers quickly categorize a function and recall its typical performance characteristics.
Furthermore, LLMs can be instrumental in explaining complexity derivation principles. A developer struggling to understand why a particular algorithm has O(N log N) complexity could ask an LLM for a step-by-step breakdown, leveraging the model's ability to synthesize information from its training data. They can also aid in documentation and code review by generating comments or explanations regarding an algorithm's expected complexity, prompting developers to verify or correct these statements. In essence, LLMs act as intelligent co-pilots, offloading the initial, pattern-based analysis and allowing human experts to focus on the more intricate, execution-dependent aspects of complexity determination.
VI. RECOMMENDED LLMS FOR CODE ANALYSIS TASKS
The choice of LLM for code analysis, including potential Big O estimations, depends on factors such as required accuracy, computational resources, data privacy concerns, and budget. Both remote, cloud-based models and local, on-premise solutions offer distinct advantages.
SUBSECTION: REMOTE, CLOUD-BASED LLMS
Remote LLMs generally offer superior performance due to their massive scale and continuous updates. GPT-4 from OpenAI is widely regarded as one of the state-of-the-art models for general reasoning and code understanding tasks. Its ability to process complex instructions and provide detailed explanations makes it a strong candidate for assisting with complexity analysis. Claude 3 Opus and Sonnet from Anthropic are another powerful family of models known for their strong performance in code-related tasks and often boast larger context windows, which can be beneficial for analyzing more extensive codebases. Gemini Advanced from Google also offers robust capabilities for multimodal and code-centric applications, providing competitive performance in code generation and analysis. Llama 3 from Meta, available through various API providers like Hugging Face or Together AI, represents a leading open-source model that, when accessed remotely, can offer competitive performance for many code analysis needs. It is important to remember that these are general-purpose LLMs; none are specifically fine-tuned for Big O analysis, so their effectiveness stems from their broad training on diverse code and documentation.
SUBSECTION: LOCAL AND ON-PREMISE LLMS
For organizations with strict data privacy requirements or those needing to fine-tune models on proprietary code, local or on-premise LLMs are a viable option. Llama 3 from Meta is an excellent choice as an open-source model that can be deployed and fine-tuned locally. Running it requires significant computational resources, but it offers complete control over data and model behavior. Mistral Large and Mistral Medium from Mistral AI are other strong open-source alternatives that provide high performance and can be run locally or accessed via their APIs. For tasks specifically geared towards code, Code Llama from Meta, which is a family of LLMs built on Llama 2 and fine-tuned for coding, and Phind-CodeLlama, a further fine-tuned version, are highly recommended. These models are specifically trained on code-related datasets, potentially giving them an edge in understanding code structure and patterns relevant to complexity analysis. The trade-off for local deployment often involves managing hardware, handling the complexities of fine-tuning, and accepting that their out-of-the-box performance might not always match the very largest cloud models without significant customization.
VII. RUNNING EXAMPLE: FINDING THE KTH LARGEST ELEMENT
To illustrate how LLMs might approach complexity analysis, let us consider the problem of finding the k-th largest element in an unsorted array. This problem is particularly illustrative because it has multiple solutions with vastly different time complexities, allowing us to examine how an LLM might analyze each approach.
SUBSECTION: APPROACH 1 - SORTING THE ARRAY
The most straightforward approach to finding the k-th largest element is to sort the entire array and then pick the element at the appropriate index.
CODE SNIPPET: Kth Largest - Sorting Approach (Partial)
def find_kth_largest_sorted(nums, k):
"""
Finds the k-th largest element in an array using sorting.
This method sorts the entire array first.
Complexity: O(N log N) due to the sorting operation.
Space: O(log N) or O(N) depending on the sort implementation
(e.g., Timsort in Python uses O(N) worst-case space).
"""
if not nums or k <= 0 or k > len(nums):
raise ValueError("Invalid input for nums or k.")
# Sort the array in ascending order. Python's list.sort() uses Timsort.
nums.sort()
# The k-th largest element will be at index len(nums) - k
# For example, if k=1 (largest), index is len(nums)-1.
# If k=len(nums) (smallest), index is 0.
return nums[len(nums) - k]
An LLM analyzing this snippet would likely recognize the `nums.sort()` call. Given its training data, it would typically know that standard library sort functions, like Python's Timsort, have an average and worst-case time complexity of O(N log N). Therefore, the LLM would likely correctly identify the overall complexity of this approach as O(N log N). This is a relatively easy task for an LLM because the complexity is encapsulated within a well-known function call whose performance characteristics are widely documented and present in training data.
SUBSECTION: APPROACH 2 - USING A MIN-HEAP (PRIORITY QUEUE)
A more efficient approach, especially when k is much smaller than N, involves using a min-heap (priority queue) to maintain the k largest elements seen so far.
CODE SNIPPET: Kth Largest - Min-Heap Approach (Partial)
import heapq
def find_kth_largest_min_heap(nums, k):
"""
Finds the k-th largest element using a min-heap (priority queue).
It maintains a min-heap of size k, storing the k largest elements.
Complexity: O(N log K) because N elements are processed,
and each heap operation (push/pop) takes O(log K) time.
Space: O(K) for storing elements in the heap.
"""
if not nums or k <= 0 or k > len(nums):
raise ValueError("Invalid input for nums or k.")
min_heap = []
for num in nums:
# Push the current number onto the heap.
heapq.heappush(min_heap, num)
# If the heap size exceeds k, remove the smallest element (root).
# This ensures the heap always contains the k largest elements encountered.
if len(min_heap) > k:
heapq.heappop(min_heap)
# After processing all numbers, the root of the min-heap is the
# k-th largest element in the original array.
return min_heap[0]
For this min-heap approach, an LLM would need to understand the `heapq.heappush` and `heapq.heappop` operations. If its training data sufficiently covers the time complexity of heap operations (O(log M) for a heap of size M), and it can correctly infer that the heap size is capped at K, then it could deduce the O(N log K) complexity. However, if the LLM treats `heapq` functions as black boxes without explicit documentation or strong pattern correlation, it might struggle to determine the logarithmic factor. This scenario highlights the LLM's reliance on learned patterns and documented knowledge rather than intrinsic understanding of data structure behavior.
SUBSECTION: APPROACH 3 - QUICKSELECT (PARTITION-BASED SELECTION)
The Quickselect algorithm is a selection algorithm that finds the k-th smallest (or largest) element in an unsorted list. It is related to QuickSort but only partitions one side of the array, leading to an average time complexity of O(N), though its worst-case is O(N^2). This approach presents a significant challenge for LLMs.
CODE SNIPPET: Kth Largest - Quickselect Partition Helper (Partial)
import random
def _partition(nums, left, right):
"""
Partitions the array segment nums[left...right] around a chosen pivot.
Elements smaller than the pivot are moved to its left, and larger
elements to its right. Returns the final index of the pivot.
The pivot is chosen randomly to mitigate worst-case scenarios.
Complexity: O(M) where M is the size of the subarray (right - left + 1).
"""
# Randomly select a pivot index within the current subarray.
# This helps to achieve average O(N) time complexity by reducing
# the chance of hitting the worst-case O(N^2) scenario.
pivot_index = random.randint(left, right)
pivot_value = nums[pivot_index]
# Move the pivot to the end of the subarray to simplify partitioning.
nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
store_index = left
# Iterate through the subarray, moving elements smaller than the pivot
# to the left side of 'store_index'.
for i in range(left, right):
if nums[i] < pivot_value:
nums[store_index], nums[i] = nums[i], nums[store_index]
store_index += 1
# Move the pivot from the end to its final sorted position.
nums[right], nums[store_index] = nums[store_index], nums[right]
return store_index
An LLM can likely analyze the `_partition` function and correctly determine its O(M) complexity, where M is the size of the subarray being partitioned, as it involves a single loop. However, the true challenge lies in analyzing the recursive `_quickselect` function (which is part of the full running example in the addendum). To determine the overall complexity of Quickselect, an LLM would need to understand the recursive call structure, how the array size is reduced in each step, and critically, the probabilistic nature of the randomized pivot selection. Distinguishing between the average-case O(N) and worst-case O(N^2) for Quickselect requires reasoning about the expected value of pivot positions over many runs, a statistical concept that LLMs, without explicit training on such derivations or an ability to simulate, are ill-equipped to handle. They might simply identify the recursive calls and the partitioning, leading to a general statement about "similar to QuickSort" or an imprecise O(N) or O(N^2) without the crucial nuance. This example starkly highlights the gap between pattern recognition and deep algorithmic reasoning.
VIII. LIMITATIONS AND FUTURE DIRECTIONS
The current generation of LLMs, while powerful, primarily functions as sophisticated pattern-matchers and statistical predictors. Their ability to determine Big O complexity is largely a reflection of their training data, allowing them to correlate code structures with known complexities. They do not possess a fundamental understanding of computation, execution semantics, or mathematical proof required for rigorous complexity analysis. This means they cannot reliably infer complexity for novel algorithms, edge cases, or scenarios where performance depends on dynamic runtime behavior or external system interactions.
Future advancements in AI could bridge some of these gaps. This might involve developing specialized LLMs fine-tuned specifically for algorithmic analysis, perhaps by integrating them with formal verification tools, static analysis engines, or symbolic execution frameworks. Such hybrid systems could potentially simulate execution paths, reason about data flow, and even perform mathematical derivations to arrive at more accurate complexity estimates. However, for the foreseeable future, true, reliable Big O complexity analysis will remain a task best performed by human experts, augmented by intelligent LLM assistants.
IX. CONCLUSION
In conclusion, Large Language Models represent a significant leap forward in AI's ability to understand and interact with code. They can offer valuable assistance in determining Big O complexity by recognizing common algorithmic patterns, leveraging documented knowledge, and providing initial hypotheses. Their strengths lie in their pattern-matching capabilities, which can quickly identify straightforward cases and known algorithms. However, their fundamental limitation is the absence of a true execution environment and the inability to perform deep, first-principles reasoning about dynamic behavior, input dependencies, or probabilistic outcomes. They cannot reliably distinguish between average and worst-case complexities in nuanced algorithms like Quickselect without explicit guidance or extensive, specific training. Therefore, while LLMs are powerful tools for enhancing developer productivity and providing insightful assistance, they should be viewed as intelligent co-pilots rather than autonomous experts in the intricate domain of algorithmic complexity analysis. Human expertise, critical thinking, and validation remain indispensable for accurate and reliable Big O determination.
ADDENDUM: FULL RUNNING EXAMPLE CODE FOR KTH LARGEST ELEMENT
FILE: kth_largest_element.py
import heapq
import random
# --- Approach 1: Sorting the Array ---
def find_kth_largest_sorted(nums: list[int], k: int) -> int:
"""
Finds the k-th largest element in an array using sorting.
This method sorts the entire array first and then picks the element
at the appropriate index.
Complexity Analysis:
- Time Complexity: O(N log N) where N is the number of elements in
'nums'. This is dominated by the sorting operation (e.g., Timsort
in Python).
- Space Complexity: O(log N) to O(N) depending on the sort
implementation. Python's Timsort uses O(N) in the worst case.
Args:
nums (list[int]): The input list of integers.
k (int): The k-th largest element to find (1-indexed).
Returns:
int: The k-th largest element.
Raises:
ValueError: If nums is empty, k is non-positive, or k is greater
than the length of nums.
"""
if not nums or k <= 0 or k > len(nums):
raise ValueError("Invalid input for nums or k.")
# Create a copy to avoid modifying the original list if not desired,
# although list.sort() sorts in-place. For this example, we'll sort
# a copy to ensure original list remains unchanged for other methods.
sorted_nums = list(nums)
sorted_nums.sort()
# The k-th largest element will be at index len(nums) - k
# Example: If k=1 (largest), index is len(nums)-1.
# If k=len(nums) (smallest), index is 0.
return sorted_nums[len(sorted_nums) - k]
# --- Approach 2: Using a Min-Heap (Priority Queue) ---
def find_kth_largest_min_heap(nums: list[int], k: int) -> int:
"""
Finds the k-th largest element in an array using a min-heap.
This method maintains a min-heap of size k, storing the k largest
elements encountered so far.
Complexity Analysis:
- Time Complexity: O(N log K) where N is the number of elements in
'nums' and K is the target rank. Each of the N elements is
processed, involving a heap push or pop operation which takes
O(log K) time.
- Space Complexity: O(K) for storing the elements in the heap.
Args:
nums (list[int]): The input list of integers.
k (int): The k-th largest element to find (1-indexed).
Returns:
int: The k-th largest element.
Raises:
ValueError: If nums is empty, k is non-positive, or k is greater
than the length of nums.
"""
if not nums or k <= 0 or k > len(nums):
raise ValueError("Invalid input for nums or k.")
min_heap = []
for num in nums:
# Push the current number onto the heap.
heapq.heappush(min_heap, num)
# If the heap size exceeds k, remove the smallest element (root)
# to maintain only the k largest elements seen so far.
if len(min_heap) > k:
heapq.heappop(min_heap)
# After processing all numbers, the root of the min-heap is the
# k-th largest element in the original array.
return min_heap[0]
# --- Approach 3: Quickselect (Partition-based Selection) ---
def _partition(nums: list[int], left: int, right: int) -> int:
"""
Partitions the array segment nums[left...right] around a chosen pivot.
Elements smaller than the pivot are moved to its left, and larger
elements to its right. Returns the final index of the pivot.
The pivot is chosen randomly to mitigate worst-case scenarios.
Complexity Analysis:
- Time Complexity: O(M) where M is the size of the subarray
(right - left + 1). It involves a single pass over the subarray.
- Space Complexity: O(1) for auxiliary variables.
Args:
nums (list[int]): The list of integers to partition (modified in-place).
left (int): The starting index of the subarray.
right (int): The ending index of the subarray.
Returns:
int: The final index of the pivot element after partitioning.
"""
# Randomly select a pivot index within the current subarray.
# This helps to achieve average O(N) time complexity by reducing
# the chance of hitting the worst-case O(N^2) scenario.
pivot_index = random.randint(left, right)
pivot_value = nums[pivot_index]
# Move the pivot to the end of the subarray to simplify partitioning.
nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
store_index = left
# Iterate through the subarray from left to right-1.
# If an element is smaller than the pivot, swap it with the element
# at 'store_index' and increment 'store_index'.
for i in range(left, right):
if nums[i] < pivot_value:
nums[store_index], nums[i] = nums[i], nums[store_index]
store_index += 1
# Move the pivot from the end to its final sorted position.
nums[right], nums[store_index] = nums[store_index], nums[right]
return store_index
def _quickselect(nums: list[int], left: int, right: int, k_target_idx: int) -> int:
"""
Recursively finds the element at k_target_idx (0-indexed smallest)
using the Quickselect algorithm. This is the core recursive function.
Complexity Analysis:
- Average Time: O(N) for the initial call, as on average, the array
is partitioned into roughly equal halves, leading to a sum of
N + N/2 + N/4 + ... which is O(N).
- Worst-Case Time: O(N^2) if the pivot selection consistently results
in highly unbalanced partitions (e.g., always picking the smallest
or largest element). Random pivot selection mitigates this.
- Space Complexity: O(log N) on average due to recursion stack depth,
O(N) in the worst-case for unbalanced partitions.
Args:
nums (list[int]): The list of integers (modified in-place).
left (int): The starting index of the current subarray.
right (int): The ending index of the current subarray.
k_target_idx (int): The 0-indexed position of the element to find.
Returns:
int: The element at the k_target_idx position.
"""
# Base case: if the subarray has only one element, it's our target.
if left == right:
return nums[left]
# Partition the array and get the pivot's final position.
pivot_index = _partition(nums, left, right)
# If the pivot is at the target index, we found our element.
if k_target_idx == pivot_index:
return nums[k_target_idx]
# If the target is in the left partition, recurse on the left side.
elif k_target_idx < pivot_index:
return _quickselect(nums, left, pivot_index - 1, k_target_idx)
# If the target is in the right partition, recurse on the right side.
else:
return _quickselect(nums, pivot_index + 1, right, k_target_idx)
def find_kth_largest_quickselect(nums: list[int], k: int) -> int:
"""
Finds the k-th largest element in an array using the Quickselect
algorithm. This algorithm is an optimized version of QuickSort
for selection problems.
Complexity Analysis:
- Average Time Complexity: O(N) where N is the number of elements.
- Worst-Case Time Complexity: O(N^2) (rare with random pivot).
- Average Space Complexity: O(log N) due to recursion stack.
- Worst-Case Space Complexity: O(N) due to recursion stack.
Args:
nums (list[int]): The input list of integers.
k (int): The k-th largest element to find (1-indexed).
Returns:
int: The k-th largest element.
Raises:
ValueError: If nums is empty, k is non-positive, or k is greater
than the length of nums.
"""
if not nums or k <= 0 or k > len(nums):
raise ValueError("Invalid input for nums or k.")
# Quickselect typically finds the k-th smallest element.
# To find the k-th largest, we need to find the (len(nums) - k)-th
# smallest element (0-indexed).
n = len(nums)
k_smallest_idx = n - k
# Create a mutable copy of the list as quickselect modifies it in-place.
mutable_nums = list(nums)
return _quickselect(mutable_nums, 0, n - 1, k_smallest_idx)
# --- Example Usage ---
if __name__ == "__main__":
example_nums = [3, 2, 1, 5, 6, 4]
k_val = 2
print(f"Original array: {example_nums}")
print(f"Finding the {k_val}-th largest element.")
print("-" * 40)
# Test Approach 1: Sorting
try:
result_sorted = find_kth_largest_sorted(example_nums, k_val)
print(f"Approach 1 (Sorting): {result_sorted}")
print(" Expected Complexity: O(N log N)")
except ValueError as e:
print(f"Error in Sorting Approach: {e}")
print("-" * 40)
# Test Approach 2: Min-Heap
try:
result_heap = find_kth_largest_min_heap(example_nums, k_val)
print(f"Approach 2 (Min-Heap): {result_heap}")
print(" Expected Complexity: O(N log K)")
except ValueError as e:
print(f"Error in Min-Heap Approach: {e}")
print("-" * 40)
# Test Approach 3: Quickselect
try:
result_quickselect = find_kth_largest_quickselect(example_nums, k_val)
print(f"Approach 3 (Quickselect): {result_quickselect}")
print(" Expected Complexity: O(N) average, O(N^2) worst-case")
except ValueError as e:
print(f"Error in Quickselect Approach: {e}")
print("-" * 40)
# Example with different k value
example_nums_2 = [7, 6, 5, 4, 3, 2, 1]
k_val_2 = 5
print(f"\nOriginal array: {example_nums_2}")
print(f"Finding the {k_val_2}-th largest element.")
try:
result_qs_2 = find_kth_largest_quickselect(example_nums_2, k_val_2)
print(f"Quickselect result: {result_qs_2}")
except ValueError as e:
print(f"Error: {e}")
