Written by: CSE Gyan Team | Last Updated: August 2026
An algorithm is a finite sequence of well-defined steps used to solve a problem or perform a computational task. In data structures, algorithms determine how information is searched, inserted, deleted, sorted, traversed, or otherwise processed.
A data structure and an algorithm are closely related. A data structure determines how data is organized, while an algorithm determines how operations are performed on that data. Choosing an appropriate combination can significantly affect the performance of a program.
For example, a collection of student records may be stored in an array, linked list, tree, or another data structure. The algorithm used to search, sort, insert, or delete those records determines how efficiently the required operation can be performed.
Algorithms are independent of a particular programming language. The same logical solution can be implemented in C, C++, Java, Python, JavaScript, or another programming language. For this reason, algorithmic thinking is an important foundation for computer science students and programmers.
An algorithm is a finite and ordered set of instructions that transforms given input into the required output. Each instruction should be sufficiently clear so that the intended operation can be performed without ambiguity.
An algorithm should describe a logical sequence of operations rather than depend on a particular programming language. A good algorithm makes it possible to understand how a problem will be solved before writing the actual program.
1. Start 2. Accept the required input 3. Process the input using defined steps 4. Produce the required output 5. Stop
Actual algorithms may contain conditions, loops, function calls, recursion, or other control mechanisms depending on the problem.
Consider an array containing several numbers. The objective is to find the largest value stored in the array. The algorithm can start by treating the first element as the current maximum and then compare the remaining elements with it.
Step 1: Start Step 2: Read an array containing n elements Step 3: Assume the first element is the maximum Step 4: Compare each remaining element with the current maximum Step 5: If an element is larger, update the maximum Step 6: Display the maximum element Step 7: Stop
If every element of the array is examined once, the number of comparisons grows with the number of elements. Therefore, the time complexity of this approach is O(n).
This example also shows the relationship between a data structure and an algorithm: the array provides the organization of the data, while the algorithm defines how that data is processed.
A useful algorithm should satisfy several fundamental properties. These properties help determine whether a proposed procedure is complete, understandable, and executable.
An algorithm may accept zero or more input values. The input provides the information required to perform the computation.
An algorithm should produce one or more meaningful results. The output represents the solution obtained after processing the input.
Every step should be precise and unambiguous. A person implementing the algorithm should not have to guess what an instruction means.
An algorithm must terminate after a finite number of steps. A procedure that continues indefinitely without producing a result does not satisfy the usual definition of an algorithm.
The operations specified by the algorithm should be basic enough to be carried out in a practical manner using available computational resources.
A data structure provides a method of organizing and storing data, whereas an algorithm provides a method for processing that data. Both are therefore important when designing an efficient solution.
| Data Structure | Algorithm |
|---|---|
| Organizes and stores data | Processes or manipulates data |
| Defines how information is represented | Defines how a problem is solved |
| Examples: Array, Stack, Queue, Tree | Examples: Binary Search, Merge Sort, BFS |
| Affects memory organization and access | Affects processing time and operations |
For example, an array can store a collection of values, while a searching algorithm determines how those values are examined to locate a required element.
The choice of algorithm becomes particularly important when the amount of data increases. A solution that works well for a small input may become inefficient when the same approach is applied to a much larger dataset.
Algorithm analysis helps developers select an approach that provides an appropriate balance between execution time, memory consumption, implementation complexity, and application requirements.
For example, repeatedly scanning an entire collection may be acceptable for a small dataset. For a large collection, a suitable data organization and searching technique may significantly reduce the amount of work.
Algorithms can be classified according to the problem they solve or the strategy used to construct the solution. These classifications can overlap. For example, an algorithm may be recursive and also use a divide-and-conquer strategy.
| Algorithm Type | Purpose | Example |
|---|---|---|
| Searching | Locates a required element in a collection. | Linear Search, Binary Search |
| Sorting | Arranges elements according to a specified order. | Merge Sort, Quick Sort |
| Traversal | Visits elements of a data structure systematically. | BFS, DFS |
| Recursive | Solves a problem using smaller instances of the same problem. | Tree Traversal |
| Greedy | Makes a locally favorable choice at each stage. | Prim's Algorithm, Kruskal's Algorithm |
| Divide and Conquer | Divides a problem into smaller parts and combines their solutions. | Merge Sort |
| Dynamic Programming | Stores results of overlapping subproblems to avoid repeated work. | Longest Common Subsequence |
Algorithm design involves selecting a strategy that matches the structure of the problem and its constraints. The following approaches are commonly studied in data structures and algorithms.
A brute-force approach systematically examines possible candidates until a valid solution is found. It is usually straightforward to understand and implement, but the number of possibilities can become large for some problems.
Linear search is a simple example because it examines elements one after another without requiring a special ordering of the input.
Divide and conquer breaks a problem into smaller subproblems, solves those subproblems, and combines their results. It is useful when a problem can be divided into similar smaller instances.
Examples: Merge Sort and Binary Search.
A greedy algorithm makes a locally favorable choice at each stage with the goal of constructing a suitable global solution. Whether the method produces an optimal result depends on the mathematical properties of the particular problem.
Examples: Prim's Algorithm and Kruskal's Algorithm.
Dynamic programming is useful when a problem contains overlapping subproblems and their results can be reused. Previously calculated results are stored so that the same subproblem does not need to be solved repeatedly.
Examples: Longest Common Subsequence and variants of the Knapsack Problem.
Note: Algorithm classification depends on the basis used. Searching and sorting classify algorithms by purpose, while greedy, divide-and-conquer, and dynamic programming describe problem-solving strategies.
Algorithm analysis evaluates how a solution behaves as the amount of input increases. Actual execution time depends on factors such as processor speed, programming language, compiler, memory hierarchy, and implementation details.
For this reason, computer science commonly studies the growth of resource requirements instead of measuring an algorithm only by its running time on one particular machine.
The two principal resources considered are:
Time complexity describes how the number of basic operations performed by an algorithm grows with the input size. It is not normally the exact number of seconds taken by a program.
Consider an operation that examines every element of an array once. If the array contains n elements, the number of examinations grows proportionally with n. Its asymptotic time complexity is therefore O(n).
The purpose of time-complexity analysis is to understand scalability. An algorithm with a lower growth rate will generally become more attractive as the input size becomes very large, although practical performance also depends on constants, implementation details, and workload.
| Complexity | Common Name | Typical Example |
|---|---|---|
| O(1) | Constant | Array access by index |
| O(log n) | Logarithmic | Binary Search |
| O(n) | Linear | Linear Search |
| O(n log n) | Linearithmic | Merge Sort |
| O(n²) | Quadratic | Simple nested-loop algorithms |
| O(2ⁿ) | Exponential | Some recursive brute-force solutions |
Space complexity describes how the memory requirement of an algorithm grows with input size. It can include temporary variables, auxiliary data structures, recursion stack, and other additional storage, depending on the analysis being performed.
For algorithm comparison, it is useful to distinguish auxiliary space from memory required simply to hold the input.
Suppose an algorithm creates an additional array containing one value for every input element. The additional storage grows with n, so its auxiliary space requirement is O(n).
| Time Complexity | Space Complexity |
|---|---|
| Describes growth in computational work. | Describes growth in memory requirements. |
| Focuses on the number of operations. | Focuses on storage used during execution. |
| Useful for evaluating execution scalability. | Useful for evaluating memory efficiency. |
| Can be affected by loops, recursion, and comparisons. | Can be affected by arrays, auxiliary structures, and recursion. |
Asymptotic notation describes the growth rate of an algorithm as the input size becomes large. It allows algorithms to be compared without depending on exact hardware or programming environment.
The three standard notations are Big O (O), Big Omega (Ω), and Big Theta (Θ).
Big O provides an asymptotic upper bound on the growth of a function. It is commonly used when discussing an algorithm's worst-case upper bound, although Big O itself is a mathematical upper-bound notation.
O(n)
Big Omega describes an asymptotic lower bound. It expresses a growth rate that the function does not fall below beyond a suitable input size.
Ω(1)
Big Theta describes a tight asymptotic bound. If an algorithm has both an O(g(n)) upper bound and an Ω(g(n)) lower bound, its growth can be described as Θ(g(n)).
Θ(n)
Big Theta describes tight asymptotic growth and should not automatically be treated as another name for average-case analysis.
| Notation | Meaning | Common Use |
|---|---|---|
| O(g(n)) | Asymptotic upper bound | Often used for worst-case upper-bound analysis |
| Ω(g(n)) | Asymptotic lower bound | Describes a minimum growth bound |
| Θ(g(n)) | Tight asymptotic bound | Describes the exact asymptotic growth order |
The performance of an algorithm can depend on the arrangement of the input. For this reason, some algorithms are studied under different input conditions.
The best case represents an input for which the algorithm performs the minimum amount of work. For example, in linear search, if the required value is found at the first position, the search can finish immediately. Its best-case running time is O(1).
The worst case represents an input for which the algorithm performs the maximum amount of work under the specified input-size conditions. In linear search, if the required value is at the final position or is absent, the algorithm may examine all n elements. Its worst-case running time is O(n).
Average-case analysis considers the expected cost over a defined distribution of inputs. It cannot be determined correctly without specifying assumptions about how inputs are distributed.
Average-case analysis is therefore different from Big Theta notation. Θ describes a tight asymptotic bound, whereas average case describes expected performance under specified input assumptions.
Searching algorithms are used to locate a required value in a collection. Two common techniques studied in data structures are Linear Search and Binary Search.
| Search Algorithm | Requirement | Best Case | Average Case | Worst Case |
|---|---|---|---|---|
| Linear Search | Data need not be sorted | O(1) | O(n) | O(n) |
| Binary Search | Appropriately sorted search space | O(1) | O(log n) | O(log n) |
The main reason Binary Search can be faster is that it uses the ordering of the data to eliminate approximately half of the remaining search space after each comparison.
Sorting algorithms arrange data according to a specified order. Different sorting techniques have different time and space requirements.
| Sorting Algorithm | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Bubble Sort* | O(n) | O(n²) | O(n²) |
| Selection Sort | O(n²) | O(n²) | O(n²) |
| Insertion Sort | O(n) | O(n²) | O(n²) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) |
*Note: The O(n) best case for Bubble Sort assumes an optimized implementation that can detect when no swaps are required. Without this optimization, its best-case running time remains O(n²).
The table illustrates why algorithm selection matters. For large datasets, an O(n log n) sorting method can scale substantially better than a simple O(n²) method, although actual performance depends on the data, implementation, and algorithm variant.
Complexity analysis becomes especially important when the input size is large. An algorithm that performs acceptably on a few hundred records may become impractical when the same approach is applied to millions of records.
Complexity analysis helps developers compare alternative solutions and understand how their resource requirements change as the input becomes larger. It can also reveal when changing the data structure or algorithm may provide a meaningful performance improvement.
Algorithms are used throughout software systems. Their role is not limited to academic examples such as searching and sorting.
Students often make mistakes by memorizing complexity values without understanding why those values occur. A better approach is to identify the dominant operation and determine how its number of executions grows with the input size.
An algorithm is a finite sequence of well-defined steps designed to solve a problem or perform a computation.
The commonly discussed characteristics are input, output, definiteness, finiteness, and effectiveness.
Time complexity describes how the computational work performed by an algorithm grows with the input size.
Space complexity describes how the memory requirement of an algorithm grows with input size. Auxiliary space is often analyzed separately from memory occupied by the input.
Big O provides an asymptotic upper bound on the growth of a function. It is commonly used to express an algorithm's worst-case upper bound.
Big O describes an asymptotic upper bound, whereas Big Theta describes a tight asymptotic bound when both upper and lower bounds have the same growth order.
Binary Search uses the ordering of the data to eliminate approximately half of the search space after each comparison, giving O(log n) worst-case time compared with O(n) for Linear Search.
Divide and Conquer divides a problem into smaller subproblems, solves them, and combines their results. Merge Sort is a common example.
Dynamic Programming stores solutions to overlapping subproblems so that the same subproblem does not need to be solved repeatedly.
It helps developers compare alternative solutions and understand how their resource requirements change as the input becomes larger.
Algorithms provide the problem-solving logic behind data-structure operations and many other areas of computer science. Learning an algorithm involves understanding its steps, assumptions, correctness, resource requirements, and suitability for a particular problem.
Time complexity and space complexity help students reason about scalability, while asymptotic notations such as O, Ω, and Θ provide standard ways to describe algorithmic growth. Searching and sorting demonstrate how different strategies can affect performance.