Past Questions

To determine the time complexity of searching for an element in a Binary Search Tree (BST), we must consider both the average case and the worst case. 1. **Average Case:** In a balanced BST (like an AVL tree or Red-Black tree), the height of the tree is O(log n). Searching for an element involves traversing from the root to a leaf, resulting in a time complexity of O(log n). 2. **Worst Case:** A standard BST does not guarantee balance. If elements are inserted in sorted or reverse-sorted order, the tree becomes 'skewed' (essentially becoming a linked list). In a skewed tree, the height of the tree is n. To find an element at the deepest leaf, the algorithm must visit every single node. 3. **Complexity Analysis:** In computer science, when a question asks for 'the time required' without specifying 'average case', it refers to the worst-case time complexity. Since the worst-case height of a BST is O(n), the search time is O(n). **Analysis of Options:** - **a. O(1):** This is the complexity for hash table lookups, not BSTs. - **b. O(log2 n):** This is the average case or the complexity for a *balanced* BST, but not for a general BST. - **c. O(n):** This is the correct worst-case time complexity for a general BST. - **d. O(n log2 n):** This is typical for sorting algorithms (like Merge Sort), not for searching a single element in a BST.

To convert an infix expression (e.g., A + B) to a postfix expression (e.g., AB+), the Shunting-yard algorithm is typically used. This algorithm requires a Stack to temporarily hold operators and parentheses. The stack is used to manage the precedence and associativity of operators: when an operator is encountered, it is pushed onto the stack if it has higher precedence than the operator currently on top; otherwise, the top operator is popped and added to the output string. Why other options are incorrect: - a. Linear list: While a stack is a type of linear list, 'Linear list' is too generic. A simple list does not inherently provide the Last-In-First-Out (LIFO) mechanism required for operator precedence management. - b. Queue: A queue follows First-In-First-Out (FIFO), which would process operators in the order they appear, ignoring mathematical precedence rules. - c. Tree: While an expression can be represented as an Expression Tree, the process of converting infix to postfix is fundamentally handled by a stack. A tree is a result or a different representation, not the primary data structure used for the conversion algorithm itself.

Hashing is a technique used to uniquely identify a specific object from a group of similar objects using a hash function. The primary goal of hashing is to map a key to a specific index in a hash table such that the time required to insert, delete, or search for an element is independent of the number of elements (n) stored in the table. 1. **O(1) - Constant Time**: In an ideal scenario (with a good hash function and minimal collisions), the hash function computes the address of the data instantly, allowing for search operations to be performed in constant time, denoted as O(1). This is the fundamental objective of using a hash table over other data structures. 2. **O(log n) - Logarithmic Time**: This is the typical search time for balanced binary search trees (BSTs) or binary search on sorted arrays. Hashing aims to be faster than this. 3. **O(n log n)**: This is common for efficient sorting algorithms (like Merge Sort or Heap Sort), not for searching in a hash table. 4. **O(n²)**: This represents quadratic time, which is highly inefficient and typical of nested loops in simple algorithms (like Bubble Sort), not a search goal.

A bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$. 1. **Fundamental Theorem**: A graph is bipartite if and only if it contains no odd cycles. This is a well-known theorem in graph theory (Kőnig's Theorem). 2. **Reasoning**: In a bipartite graph, any path that starts in set $U$ and returns to set $U$ must traverse an even number of edges (U -> V -> U). Therefore, any cycle (a path that starts and ends at the same vertex) must have an even length. If a graph contains a cycle of odd length (e.g., a triangle), it is impossible to partition the vertices into two sets without having an edge connect two vertices within the same set. **Analysis of Options:** - **Option a (n edges):** The number of edges does not determine if a graph is bipartite. A bipartite graph can have anywhere from 0 to $n^2/4$ edges. - **Option b (a cycle of odd length):** This is the exact opposite of the requirement. If a graph has an odd cycle, it is NOT bipartite. - **Option c (no cycle of odd length):** This is the correct mathematical definition/property of a bipartite graph. - **Option d (n^2 edges):** A simple graph with $n$ nodes can have at most $n(n-1)/2$ edges. $n^2$ edges are impossible for a simple graph, and the number of edges alone does not define bipartiteness.

To determine which algorithm does not have a worst-case running time of O(n²), we analyze the time complexity of each option: 1. **Insertion Sort**: In the worst case (when the input array is sorted in reverse order), every element must be compared and shifted across the entire sorted portion of the array. This results in a time complexity of O(n²). 2. **Merge Sort**: This is a divide-and-conquer algorithm. It recursively divides the array into halves (log n levels of recursion) and merges them back together in linear time (n). Therefore, its time complexity is O(n log n) in all cases, including the worst case. Since O(n log n) is asymptotically smaller than O(n²), it does not have a worst-case running time of O(n²). 3. **Quick Sort**: While its average case is O(n log n), its worst case occurs when the pivot is consistently the smallest or largest element (e.g., on an already sorted array without random pivot selection). This leads to a time complexity of O(n²). 4. **Bubble Sort**: This algorithm uses nested loops to repeatedly swap adjacent elements. In the worst case (reverse sorted), it performs approximately n²/2 comparisons and swaps, resulting in a time complexity of O(n²). Conclusion: Merge Sort is the only algorithm among the choices that guarantees a worst-case performance better than O(n²).

In indexed addressing mode, the effective address (EA) of the operand is calculated by adding the contents of an index register (X) to the address field (displacement/offset) provided in the instruction. The formula is: EA = Content of Index Register + Address Field. If the address field consists of all 0's bits, the formula becomes: EA = Content of Index Register + 0, which simplifies to EA = Content of Index Register. This means the instruction is using the value stored in the register as the memory address to access the operand. This is the definition of Register Indirect Addressing, where the register holds the pointer to the memory location of the operand. Why other options are incorrect: - b. Register Direct: In this mode, the operand itself is stored in the register, not at a memory address pointed to by the register. - c. Memory Indirect: This involves accessing memory twice (once for the address and once for the operand), which is not the case here. - d. Base-register addressing: While similar to indexed addressing, base-register addressing typically uses a base register to point to the start of a segment and a non-zero offset to find a specific element; if the offset is zero, it still functions as a register indirect access, but the specific mechanism described (indexed operand with 0 offset) is the classic definition of transforming indexed mode into register indirect mode.

To determine the length of the instruction, we need to calculate the number of bits required for each component of the instruction: the opcode and the two memory address operands. 1. **Opcode bits**: The number of operation codes is 150. To represent 150 distinct operations, we need $\lceil \log_2(150) \rceil$ bits. Since $2^7 = 128$ and $2^8 = 256$, we need 8 bits for the opcode. 2. **Memory Address bits**: The memory size is 1M byte. $1\text{M} = 2^{20}$ bytes. Therefore, a full memory address requires 20 bits. 3. **Extended Memory Address (Displacement)**: The problem specifies the use of a base register of length 12 bits. In a base-displacement addressing mode, the effective address is calculated as: $\text{Effective Address} = \text{Base Register} + \text{Displacement}$. To reach any location in a 20-bit address space using a 12-bit base register, the displacement (the part stored in the instruction) must be able to cover the remaining range. $\text{Displacement bits} = \text{Total Address bits} - \text{Base Register bits} = 20 - 12 = 8$ bits. 4. **Total Instruction Length**: The instruction has two such extended memory address operands. $\text{Total Length} = \text{Opcode bits} + (2 \times \text{Displacement bits})$ $\text{Total Length} = 8 + (2 \times 8) = 8 + 16 = 24$ bits. **Correction/Re-evaluation based on standard exam interpretation**: In many competitive exam contexts for this specific question, 'extended memory address' is interpreted as the full address required to index the memory if the base register is used as a pointer to a segment or if the displacement is treated as the primary address component. However, if we look at the options provided (16, 20, 24, 32), and the standard architecture of such problems, if the 'extended' part implies the full address is needed or if the base register is used to offset a larger block, the calculation changes. If the instruction requires the full 12-bit base register reference (to select which base register to use) plus the displacement, or if the displacement itself is larger: Let's re-examine: If the 'base register of length 12' refers to the number of bits used to *address* the base register (i.e., $2^{12}$ base registers), then the displacement would be the full 20 bits. That would be too large. If the displacement is 12 bits (matching the base register length) and the opcode is 8 bits: $8 + 12 + 12 = 32$ bits. This matches option (a). In this interpretation, the 'base register of length 12' implies the offset/displacement field provided in the instruction is also 12 bits to complement the base register's scale. Given the options, the most logically consistent architectural fit for a 32-bit instruction is: Opcode (8 bits) + Operand 1 (12 bits) + Operand 2 (12 bits) = 32 bits.

Indexing establishes an index (or indexed organization) to allow fast access without sorting file.

In a linked list, elements are not stored in contiguous memory locations; instead, each node contains a pointer to the next node. Because there is no direct index-based access (unlike an array), the only way to search for a specific element is to perform a 'Linear Search'. This involves starting at the head node and traversing the list sequentially one node at a time until the target element is found or the end of the list is reached. In the worst-case scenario (where the element is at the very end of the list or not present at all), the algorithm must visit all 'n' nodes. Therefore, the time complexity is proportional to the number of elements, which is expressed in Big O notation as O(n). Why other options are incorrect: - O(log2 n): This is the complexity of a Binary Search. Binary search requires random access to the middle element, which is not possible in a standard linked list. - O(1): This is constant time. This would only be possible if we had a direct pointer to the element we were searching for. - O(n2): This is quadratic time, typically associated with nested loops (like Bubble Sort). Searching a list only requires a single pass.

To determine the operand fetching time, we must analyze the number of memory accesses required to retrieve the actual operand for each addressing mode. Memory access is significantly slower than register access. 1. **Minimum Fetching Time:** - **Immediate Addressing:** The operand is part of the instruction itself. No separate fetch is needed after the instruction is fetched. - **Register Direct Addressing:** The operand is stored in a CPU register. Accessing a register is the fastest possible way to retrieve data. - Between these two, Immediate is technically fastest (part of the instruction stream), but Register Direct is also extremely fast. Both are candidates for the 'minimum' side of the pair. 2. **Maximum Fetching Time:** - **Direct Addressing:** Requires 1 memory access. - **Indirect Addressing (Memory Indirect):** The instruction contains the address of a memory location, which in turn contains the address of the operand. This requires **two** memory accesses to get the operand. - **Indexed/Base-displacement:** Usually requires 1 memory access (after a quick ALU calculation). 3. **Evaluating the Options:** - **Option (a): Register Direct (Fast) and Memory Indirect (Slowest).** This pair correctly identifies a very fast mode and the slowest common mode (due to double memory indirection). - **Option (b): Immediate (Fast) and Indexed Indirect.** While Indexed Indirect is slow, 'Memory Indirect' is the classic textbook example of maximum latency in basic architecture questions. - **Option (c): Register Direct (Fast) and Indexed (Moderate).** Indexed is faster than Indirect. - **Option (d): Immediate (Fast) and Base-displacement (Moderate).** Base-displacement is faster than Indirect. - **Option (e): Immediate (Fast) and Extended Memory (Moderate).** Extended memory usually refers to a larger address space but still typically involves only one memory access per operand fetch. Conclusion: Memory Indirect requires the most memory references (two), making it the maximum fetching time mode. Register Direct (or Immediate) represents the minimum. Option (a) provides the most distinct contrast between the fastest and slowest mechanisms.

The question describes the fundamental property of a Max-Heap. A Heap is a specialized complete binary tree. In a Max-Heap, for any given node, the value of that node is greater than or equal to the values of its children (the subtree below it). Heap Sort utilizes this data structure by building a max-heap and repeatedly extracting the maximum element (the root) to sort the array. Why other options are incorrect: - a. Selection Sort: This is a comparison-based sort that repeatedly finds the minimum element from the unsorted part and puts it at the beginning. It does not use a tree structure. - b. Insertion Sort: This builds the final sorted array one item at a time by shifting elements. It does not use a tree structure. - d. Quick Sort: While Quick Sort uses a divide-and-conquer approach that can be visualized as a recursion tree, it does not maintain a binary tree where a parent is always larger than its subtree; it partitions elements based on a pivot.

1. Understanding the Data Structure: An adjacency matrix for a graph with 'n' vertices is a 2D array of size n x n. If there is an edge between vertex i and vertex j, the cell matrix[i][j] is set to 1 (or the weight of the edge); otherwise, it is 0. 2. Defining the Degree: In an undirected graph, the degree of a vertex is the total number of edges connected to it. 3. Process to find the Degree: To find the degree of a specific vertex 'v', we must examine the entire row (or column) corresponding to that vertex in the adjacency matrix. This involves checking every cell from matrix[v][0] to matrix[v][n-1]. 4. Time Complexity Analysis: Since there are 'n' columns in the row for vertex 'v', the algorithm must perform 'n' operations (checks/additions) to count the number of 1s. Therefore, the time complexity is proportional to the number of vertices, which is O(n). 5. Evaluating other options: - O(e): This would be the complexity if we were iterating through an edge list. - O(n²): This is the time required to find the degrees of ALL vertices or to initialize the matrix, not a single vertex. - O(e+n): This is typical for graph traversal (like BFS or DFS) using an adjacency list, not for finding a single vertex's degree in a matrix.

Binary Insertion Sort is a variation of the standard Insertion Sort. In a standard Insertion Sort, the algorithm searches for the correct position to insert the current element using linear search. In Binary Insertion Sort, binary search is used to find the correct position, reducing the number of comparisons from O(n) to O(log n) per element. However, the time complexity of an algorithm is determined by the sum of all its operations. While binary search reduces the number of comparisons to O(n log n) in total, the algorithm still requires shifting elements to make room for the inserted element. In the worst case (e.g., when the input array is sorted in reverse order), for every element inserted, we must shift all previously sorted elements. 1. Comparisons: O(n log n) due to binary search. 2. Swaps/Shifts: O(n^2) because in the worst case, we shift (1 + 2 + 3 + ... + n-1) elements. Since the shifting operation dominates the comparison operation, the overall worst-case time complexity remains O(n^2). Analysis of options: - a. O(n): This is the best-case complexity for standard insertion sort (already sorted array), but not the worst case. - b. O(n log2 n): This is the complexity of the comparisons only, not the total time including shifts. - c. O(n 1.2): This is not a standard complexity for this algorithm. - d. O(n2): Correct, as the shifting of elements takes quadratic time.

In graph theory and data structures, a tree is defined as an undirected graph that is connected and acyclic. Let's evaluate each option: - Option (a): Every tree is a bipartite graph. This is TRUE. A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent. Since a tree has no cycles (and specifically no odd-length cycles), it can always be 2-colored, making it bipartite. - Option (b): A tree contains a cycle. This is FALSE. By definition, a tree is an acyclic graph. If a graph contains a cycle, it cannot be a tree. - Option (c): A tree with n nodes contains n-1 edges. This is TRUE. This is a fundamental property of trees; any connected graph with n vertices and n-1 edges is necessarily a tree. - Option (d): A tree is a connected graph. This is TRUE. By definition, a tree must be connected. A collection of disjoint trees is called a 'forest'. Since the question asks for the FALSE statement, option (b) is the correct answer.

Linear search is the simplest searching algorithm. It works by starting at the first element of an array and comparing the target value with each element sequentially until a match is found or the end of the array is reached. 1. **Best Case Complexity**: O(1) - This occurs if the target element is the first element of the array. 2. **Worst Case Complexity**: O(n) - This occurs if the target element is the last element of the array or is not present at all. In this case, the algorithm must perform 'n' comparisons for an array of size 'n'. 3. **Average Case Complexity**: O(n) - On average, the element will be found in the middle (n/2), which simplifies to O(n) in Big O notation. Analysis of other options: - O(log2 n) is the complexity of Binary Search, which requires the array to be sorted. - O(n log2 n) is typical for efficient sorting algorithms like Merge Sort or Quick Sort. - O(n^2) is typical for simple sorting algorithms like Bubble Sort or Selection Sort.

Recursion occurs when a function calls itself. To manage these nested calls, the computer must keep track of where to return after a function call completes, as well as the local variables and parameters for each specific call. This is handled by a system data structure called the 'Call Stack'. 1. When a recursive function is called, a new 'stack frame' (containing the return address, arguments, and local variables) is 'pushed' onto the stack. 2. This process continues until the base case is reached. 3. Once the base case is satisfied, the function begins to return, and the stack frames are 'popped' off the stack in Last-In-First-Out (LIFO) order, returning control to the previous call. Why other options are incorrect: - a. Queues: These follow First-In-First-Out (FIFO) logic, which would return the first call made before the most recent call, breaking the logic of nested recursion. - c. Linked lists: While a stack can be implemented using a linked list, a linked list itself is a general-purpose linear structure and not the specific mechanism used for procedure implementation. - d. Strings: These are sequences of characters used for text representation and have no mechanism for managing function execution flow.

Base-displacement addressing mode (also known as Base-Offset addressing) calculates the effective address by adding a constant value (displacement) to the contents of a base register. 1. **Program Relocatability (Option c):** This is a primary advantage of base-displacement addressing. Because the program refers to memory locations relative to a base register rather than using absolute addresses, the entire program can be loaded into any part of the physical memory. The OS only needs to update the base register to point to the start of the allocated memory block, making the code 'relocatable'. 2. **Addressing Large Memory with Small Fields (Option d):** In an N-word memory, a direct address would require log2(N) bits. However, by using a base register to hold the high-order bits of the address and a small displacement field in the instruction for the low-order bits, the instruction length can be significantly reduced. This allows the CPU to address a large memory space without requiring a massive address field in every single instruction. Since both (c) and (d) are fundamental strengths of this addressing mode, option (e) is the correct choice.

The question describes a linear data structure with a specific access restriction: elements can only be added (pushed) or removed (popped) from one end. This is the fundamental definition of a Stack, which follows the LIFO (Last-In, First-Out) principle. Analysis of options: - a. Stack: Correct. It restricts insertion and deletion to a single end called the 'top'. - b. Memory: Incorrect. Memory refers to the physical or virtual storage space (RAM) where data is kept, not a specific logical data structure with access restrictions. - c. Linked List: Incorrect. A linked list is a general linear collection of nodes where elements can typically be added or removed from both ends or any position in the list, provided the pointer is known. - d. Heap: Incorrect. A heap is a specialized tree-based data structure that satisfies the heap property (max-heap or min-heap). While it has specific rules for insertion and deletion to maintain its structure, it does not restrict access to a single 'end' in the linear sense described.

Step-by-step analysis of the options: 1. **Option (a): 'allows simultaneous access to multiple files'** - This is correct. A DBMS provides concurrency control mechanisms that allow multiple users or applications to access and modify data stored across various files/tables simultaneously without compromising data integrity. 2. **Option (b): 'can do more than a record management system'** - This is correct. A Record Management System (RMS) or a traditional File Processing System is limited to basic CRUD operations on individual files. A DBMS adds sophisticated layers such as data independence, transaction management (ACID properties), complex querying (SQL), security, and relationship management between different data entities. 3. **Option (c): 'is a collection of programs for managing data in a single file'** - This is incorrect. A DBMS is designed to manage large volumes of data that are typically spread across multiple files, tables, and indices. Limiting it to a 'single file' describes a simple flat-file system, not a full DBMS. Since both (a) and (b) are accurate descriptions of the capabilities and nature of a Database Management System, the correct choice is (d).

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one. 1. **Step-by-step Analysis**: - In the first step, the algorithm compares the target key with the middle element of the array. - If the key is not found, the search space is reduced by half (either the left half or the right half is discarded). - This process repeats: the size of the search space goes from n → n/2 → n/4 → ... → 1. 2. **Mathematical Derivation**: - Let 'k' be the number of iterations. The size of the array after k iterations is n / (2^k). - The search terminates when the size of the array becomes 1: n / (2^k) = 1. - Solving for k: 2^k = n, which means k = log2(n). 3. **Evaluating Options**: - **Option a: O(log2 n)**: Correct. This represents the logarithmic time complexity of binary search. - **Option b: O(n)**: Incorrect. This is the time complexity of Linear Search, where every element is checked one by one. - **Option c: O(n log2 n)**: Incorrect. This is typical of efficient sorting algorithms like Merge Sort or Quick Sort, not searching. - **Option d: O(n2)**: Incorrect. This is typical of simple sorting algorithms like Bubble Sort or Selection Sort.

The question describes a data structure that follows the First-In-First-Out (FIFO) principle. 1. **Queues**: A queue is a linear data structure where elements are inserted at one end (called the 'rear' or 'tail') and removed from the other end (called the 'front' or 'head'). This matches the description perfectly. 2. **Stacks**: A stack follows the Last-In-First-Out (LIFO) principle. Both insertion (push) and deletion (pop) occur at the same end, known as the 'top'. 3. **Tree**: A tree is a non-linear, hierarchical data structure, not a linear list. 4. **Deque (Double-Ended Queue)**: A deque allows insertion and deletion from both the front and the rear ends, which is more flexible than the specific restriction described in the question.

The question describes the fundamental mechanism of the Bubble Sort algorithm. 1. **Bubble Sort**: This algorithm works by repeatedly stepping through the list, comparing each pair of adjacent elements, and swapping them if they are in the wrong order (e.g., if the left element is greater than the right element in an ascending sort). This process is repeated until the largest element 'bubbles up' to its correct position at the end of the list. 2. **Why other options are incorrect**: - **Insertion Sort (a)**: This algorithm builds the final sorted array one item at a time by taking an element and inserting it into its correct position among the already-sorted elements. It does not simply swap adjacent elements throughout the list. - **Heap Sort (b)**: This is a comparison-based sorting technique based on a Binary Heap data structure. It involves building a max-heap and repeatedly extracting the maximum element; it does not rely on adjacent element comparisons. - **Quick Sort (c)**: This is a divide-and-conquer algorithm that picks an element as a 'pivot' and partitions the given array around the picked pivot. While it involves swapping, it is not limited to adjacent elements.

Bubble Sort is a simple comparison-based sorting algorithm. It works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. 1. **Mechanism**: In the first pass, the algorithm performs (n-1) comparisons to move the largest element to the end of the list. In the second pass, it performs (n-2) comparisons, and so on. 2. **Worst-Case Scenario**: The worst case occurs when the input array is sorted in reverse order. In this scenario, the algorithm must perform the maximum number of comparisons and swaps for every single pass. 3. **Mathematical Calculation**: The total number of comparisons is the sum of the first (n-1) integers: (n-1) + (n-2) + ... + 1 = [n(n-1)] / 2. 4. **Complexity**: Expanding this gives (n^2 - n) / 2. In Big O notation, we drop constant coefficients and lower-order terms, resulting in a time complexity of O(n^2). Analysis of other options: - O(1) represents constant time, which is impossible for sorting n elements. - O(log2 n) represents logarithmic time, typically seen in binary search, not sorting. - O(n) represents linear time, which is the best-case complexity for an optimized Bubble Sort (when the array is already sorted), but not the worst case.

In a full binary tree (also known as a proper or plane binary tree), every node has either 0 or 2 children. Let 'n' be the number of leaf nodes and 'i' be the number of internal nodes. 1. Total number of nodes (N) = i + n. 2. In any binary tree, the number of edges is N - 1. 3. In a full binary tree, every internal node has exactly 2 children, so the total number of edges is also 2 * i. 4. Therefore, 2i = N - 1. 5. Substituting N = i + n into the equation: 2i = (i + n) - 1. 6. Solving for i: i = n - 1. 7. Now, substitute i back into the total nodes equation: N = (n - 1) + n = 2n - 1. Example: If a full binary tree has 3 leaves (n=3), it must have 2 internal nodes (i=2), totaling 5 nodes (2*3 - 1 = 5).

The question asks for the time complexity to find the shortest path in a graph with n vertices and e edges. In the context of standard competitive exams for CSE, this typically refers to the Single Source Shortest Path (SSSP) problem using Dijkstra's Algorithm. 1. Dijkstra's Algorithm using a simple array (linear search for the minimum distance vertex) has a time complexity of O(n^2). This is the most basic implementation and is optimal for dense graphs where e is close to n^2. 2. Dijkstra's Algorithm using a Binary Heap has a complexity of O(e log n). 3. Dijkstra's Algorithm using a Fibonacci Heap has a complexity of O(e + n log n). Looking at the provided options: - O(e) and O(n) are too low for general shortest path algorithms. - O(e^2) is not a standard complexity for these algorithms. - O(n^2) is the standard complexity for the basic implementation of Dijkstra's algorithm. While O(e log n) is often more efficient for sparse graphs, among the given choices, O(n^2) is the only mathematically recognized complexity for a standard shortest path algorithm (Dijkstra's) implementation.