Time Complexity in Data Structure
FREE
Overview
Time complexity in data structure is a measure of how the number of operations an algorithm performs grows as the input size n grows. It is written in asymptotic notation such as O(1), O(log n), O(n) or O(n²). It ignores hardware and language speed, so you can compare algorithms and data-structure operations fairly.
Time complexity matters in three situations: choosing the right data structure for an operation you will run millions of times, answering exam and GATE questions in DAA (Design and Analysis of Algorithms), and reasoning about performance in coding interviews. What you'll learn in this article: a complexity cheat-sheet table for common data-structure operations, the types of time complexity from O(1) to O(2ⁿ) with examples, how to calculate complexity from code patterns, and how to solve recurrences with the Master theorem.’
Takeaways
- Time complexity measures how the number of basic operations grows with input size n, not the seconds an algorithm takes.
- Big O, Omega and Theta are bounds (upper, lower and tight); best, average and worst case describe the input being analysed. They are not the same thing.
- The cheat-sheet table below gives the access, search, insertion and deletion complexity for the data structures that appear in every exam and interview.
- For recursive algorithms, write a recurrence such as T(n) = 2T(n/2) + n and solve it with a recursion tree or the Master theorem.
What is Time Complexity in Data Structure?
To answer this question first we must keep in mind that for number of problems that must be solved using an algorithm, there can be infinte number of solutions. And it then becomes important to do the analysis of algorithms to find the most efficient solution for solving that problem.
Now to know which solution is the most efficient one, the concept of space and time complexity of algorithms comes into picture.
The Space and Time complexity can be defined as a measurement scale for algorithms where we compare the algorithms on the basis of their Space (i.e. the amount of memory it utilises ) and the Time complexity (i.e. the number of operations it runs to find the solution).
There can more than one way to solve the problem in programming, but knowing how which of the algorithm works efficiently and hence, can add value to the way we do programming .
So, in order to dive deep to find the effectiveness of the program, we must know how to evaluate them using the Space and Time complexity. This use of Space and Time complexity can help us make the program behave according to the required optimal conditions, which in some way makes us an efficient programmers too. As with this module we are focussing more on the Time Complexity domain let us take a look at the definition of the same.
Time Complexity Definition: The Time complexity can be defined as the amount of time taken by an algorithm to execute each statement of code of an algorithm till its completion with respect to the function of the length of the input.
The Time complexity of algorithms is most commonly expressed using the big O notation. It's an asymptotic notation to represent the time complexity. We will study about it in detail in the next tutorial.
The Time Complexity can also be elaborated by estimating the counts of the number of elementary steps that are performed by any algorithm to finish the execution. As we saw in above example where we shared the two approaches to find a square of a number, then with the first approach the time taken will remain constant while for the second it varies with respect to the 'n' that runs on the loop to give an output.
It should also be noted that as the algorithm's performance varies with respect to the multiple types of input data, so we usually we also keep a check for the worst-case scenario for an algorithm so that we are well aware of the maximum time taken for any input size.
Summing up above points, we can concude that the time complexity is explained as the number of operations an algorithm performs in order to complete a task with respect to the size of the input. And to find out which algorithm must be considered as the most efficient one, we pick the one which takes the smallest number of operations in terms of the time complexity.
Build an AI-First Career, Master the Complete Skillset
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
AI Forward Deployed Engineer Program
Full-stack engineering, production AI and client-facing consulting
+1000 moreTime Complexity vs Actual Running Time
Two programs solving the same problem can have the same time complexity but very different running times, because running time depends on factors that time complexity deliberately ignores:
| Factor | Affects running time? | Affects time complexity? |
|---|---|---|
| Hardware (CPU, RAM speed) | Yes | No |
| Programming language | Yes | No |
| Compiler / interpreter quality | Yes | No |
| Input size (n) | Yes | Yes |
This is exactly why we count operations as a function of n: the count is portable across machines, while seconds are not.
Asymptotic Notations: Big O, Big Omega (Ω) and Big Theta (Θ)
- Big O(expression): Big O gives an upper bound on how a function grows. It means the function grows no faster than the expression, up to a constant factor. See the formal NIST definition of Big-O notation.
Omega(expression): Big Omega (Ω) gives a lower bound on how a function grows. It means the function grows no slower than the expression, up to a constant factor.
- Theta(expression): Big Theta (Θ) gives a tight bound: the function grows at the same rate as the expression both from above and below (it lies in both O and Ω).
Big O is not the same as worst case. Big O, Ω and Θ are bounds on a function. Best, average and worst case describe which input we analyse. You can state a Big-O, Ω or Θ bound for any of the three cases: insertion sort's worst case is Θ(n²) and its best case is Θ(n), so a bound and a case are two different statements about the same algorithm. This confusion costs marks in university exams and comes up in interviews.
| Notation | Meaning | Read as · example |
|---|---|---|
| Big O (upper bound) | grows at most this fast | "at most quadratic" · O(n²) |
| Big Ω (lower bound) | grows at least this fast | "at least linear" · Ω(n) |
| Big Θ (tight bound) | grows exactly at this rate | "exactly n log n growth" · Θ(n log n) |
Types of Time Complexity (With Examples)
Every complexity class below answers one question: how does the work grow as n grows? From fastest to slowest, the ordering is O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).
Constant Time – O(1)
The work does not depend on n at all. Example: reading arr[5] from an array, or a hash-table lookup on average. When you see it: a single operation, or a fixed number of operations, regardless of how big the input is.
Logarithmic Time – O(log n)
The work grows one step each time the input is halved. Example: binary search on a sorted array. When you see it: each step halves the search space, so 1,000,000 items need about 20 steps.
Linear Time – O(n)
The work grows in direct proportion to n. Example: linear search, or traversing a linked list node by node. When you see it: a single loop that touches every element once.
Linearithmic Time – O(n log n)
An n-sized amount of work repeated across log n levels. Example: merge sort and heap sort. When you see it: a recursion that splits the input in half (log n levels) and does linear work to merge each level.
Quadratic Time – O(n²)
The work grows with every pair of elements. Example: bubble sort, or two nested loops over the same array. When you see it: a loop inside a loop, both running n times.
Exponential Time – O(2ⁿ)
The work doubles with each additional input element. Example: naive recursive Fibonacci, or enumerating all subsets of a set. When you see it: every call spawns two or more smaller calls over the same data.
How Scaler Transformed Careers in Different Fields
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ moreTime Complexity of Common Data Structure Operations (Cheat Sheet)
How to read this table: values are the average case unless a worst case is shown in brackets. Access means reaching an element by position; search means finding an element by value.
| Data structure | Access · search | Insertion · deletion |
|---|---|---|
| Array | O(1) · O(n) | O(n) · O(n) |
| Singly Linked List | O(n) · O(n) | O(1) at head · O(1) at head |
| Doubly Linked List | O(n) · O(n) | O(1) at either end · O(1) given the node |
| Stack (push/pop) | O(n) · O(n) | O(1) · O(1) |
| Queue (enqueue/dequeue) | O(n) · O(n) | O(1) · O(1) |
| Hash Table | N/A · O(1) avg [O(n) worst] | O(1) avg [O(n) worst] · O(1) avg [O(n) worst] |
| Binary Search Tree | O(log n) avg [O(n) worst] · O(log n) avg [O(n) worst] | O(log n) avg [O(n) worst] · O(log n) avg [O(n) worst] |
| AVL / Red-Black Tree | O(log n) · O(log n) | O(log n) · O(log n) |
| Binary Heap (min/max) | O(1) for min/max · O(n) | O(log n) · O(log n) for extract-min/max |
Why does a BST degrade to O(n)? When keys are inserted in sorted order, each new node becomes the right child of the last one, and the tree turns into a "linked list". Balanced trees such as AVL trees rotate on insert to prevent this, which is why their worst case stays O(log n).
Time Complexity of Sorting Algorithms
The Time complexity of sorting algorithms can be elaborated as the best posiible way to pick out the best sorting technique in a situation. Understanding the time complexities with respect to the sorting algorithms can help us in picking up the best sorting technique, listed below are few of them:
-
The Time Complexity of Insertion Sort: The time complexity of Insertion Sort is Ω(n) in its best case possible and O(n^2) in its worst case possible. It has been observed that for very small 'n',the Insertion Sort is faster than more efficient algorithms such as Quick sort or Merge Sort.
-
The Time Complexity of Merge Sort: The time complexity of Merge Sort is Ω(nlogn) in its best case possible and O(nlogn) in its worst case possible. This can be explained as in merge sort implements the same number of sorting steps for all kinds of cases. Out of all the sorting technique, the merge sort has the most stable time complexity for all kinds of cases because the steps which are executed for all kinds of cases are same.
-
The Time Complexity of Quick Sort: The time complexity of Quick Sort is Ω(nlogn) in its best case possible and O(n^2) in its worst case possible. As we know QuickSort is a Divide and Conquer algorithm where the element is picked as a pivot and partitions are made on the given array around the picked pivot. This makes it the fastest of the sorting algorithms as due to its performance in best case and alos in average cases are said to of O(nlogn).
-
The Time Complexity of Bubble Sort: The time complexity of Bubble Sort is Ω(n) in its best case possible and O(n^2) in its worst case possible. As is widely known that the The Time Complexity of Bubble Sort is a reliable sorting algorithm as runs through the list repeatedly, compares adjacent elements, and swaps them if they are out of order. This process is repeated until the list is sorted and hence, this is also considered the simplest sorting algorithm.
Time Complexity of Searching Algorithms
The Time complexity of searching algorithms can be elaborated as checking for an element or retrieving an element from any data structure where it was once stored. Understanding the time complexities with respect to the searching algorithms can help us in picking up the best searching technique and analyse which of them is faster, listed below are few of them:
-
The Time Complexity of Linear Search: The Time Complexity of Linear Search has the best case defined by Ω(1) and the worst case defined by O(n). Here we can see that the Linear Search follows the sequential access.
-
The Time Complexity of Binary Search: The Time Complexity of Binary Search has the best case defined by Ω(1) and the worst case defined by O(log n). Binary Search is the faster of the two searching algorithms. However, for smaller arrays, linear search does a better job.
Example to demonstrate the Time complexity of searching algorithms:
let us dive deep into this following example to understand more on the Time complexity of searching algorithms. Here we shall be comparing two different algorithms which were used to solve a problem. Now the problem that we are talking here is searching.
Let us assume here that we have a sorted array in ascending order and we need to search for a particular element in this array. Now to solve this problem we have two algorithms:
1. Linear Search.
2. Binary Search.
Consider an array which contains five elements, and we have to find the number 24 in the array.
Now when we search via the Linear search algorithm, it will compare each element of the array to the specific search_value. Now when the search_value is found, it shall return true. Seems simple right!
Now let’s analyse the count of the number of operations that it needs to performs to return its output. We find the answer to this as 5 as it compares every element of the array one by one. We can now say that by linear search it uses five operations (the maximum number of operations) to find the given element. This is also the worst case of an algorithm in the case of Linear search.
Summing up, The Linear search takes 'n' (where n is the size of the array) number of operations in its worst case.
Now Let’s examine the Binary search algorithm by diving deep into a simple example.
Now for the given array , if we were to find the search_value then by the binary search algorithm we first check the middle of the array. Now as middle of array is 24, we then check 24>21 so we start searching left, then by searching elements to the left we see that we will find the number say 7, then as 7<21 then we start searching to the desired element and once we see 21, then we compare 21=21.
We see that when we count number of operations binary search took to find the desired element was four operations. This justify that there is a logarithmic approach for the binary search.
Standard representation when we search through binary search algorithm can be represented as ,
For an array of size n, the number of operations performed by the Binary Search is: log(n)
How to Compare Algorithms?
When we want to find out what are the parameters to compare algorithms in the time complexity domain, listed below are the three points which must be evaluated to compare the algorithms:
1. The Execution Time: The execution time can be one of the measure but majorly this also gets manipulated to the particular computer we are using so this measure can be one of the aspect but not the only aspect to define and compare algorithms.
2. The number of statements executed: The number of statements executed can too vary with respect to which expertise the programmer is having as well as the number of statements varies with the programming language. Again, this measure can be one of the aspect but not the only aspect to define and compare algorithms.
3. The Ideal solution: When we want to the express the running time of a given algorithm with respect to the function of the input size lets say ,'f(n)'. Now to compare these different functions corresponding to running times we see that this type of comparison are independent of machine time, programming style, etc.
Code with Confidence! Enroll in Scaler Academy's Data Structures Course and Master Efficient Algorithms.
Turn Learning into Career Growth
Conclusion
-
The Time complexity can be defined as the amount of time taken by an algorithm to execute each statement of code of an algorithm till its completion with respect to the function of the length of the input.
-
The three important asymptotic notations of Time complexity are:
O: This notations defines if functions grow slower than or at the same rate with respect to the expression.
Ω: This notations defines if functions grow faster than or at the same rate with respect to the expression.
Θ: This notations defines if functions' growth lie in both O and Ω.
-
The different types of Time complexity of sorting algorithms are:
-
The Time Complexity of Insertion Sort : The time complexity of Insertion Sort is Ω(n) in its best case possible and O(n^2) in its worst case possible.
-
The Time Complexity of Merge Sort : The time complexity of Merge Sort is Ω(nlogn) in its best case possible and O(nlogn) in its worst case possible.
-
The Time Complexity of Quick Sort: The time complexity of Quick Sort is Ω(nlogn) in its best case possible and O(n^2) in its worst case possible.
-
The Time Complexity of Bubble Sort : The time complexity of Bubble Sort is Ω(n) in its best case possible and O(n^2) in its worst case possible.
-
-
The Time complexity of searching algorithms can be elaborated as checking for an element or retrieving an element from any data structure where it was once stored.
-
The different types of Time complexity of searching algorithms are:
a. The Time Complexity of Linear Search: The Time Complexity of Linear Search has the best case defined by Ω(1) and the worst case defined by O(n).
b. The Time Complexity of Binary Search: The Time Complexity of Binary Search has the best case defined by Ω(1) and the worst case defined by O(log n).
FAQs
What is time complexity in data structure?
Time complexity is the amount of work an algorithm or data-structure operation does as the input size n grows. It is measured by counting basic operations, not seconds, and written in asymptotic notation such as O(1), O(log n) or O(n²). This lets you compare approaches independently of hardware or programming language.
What are the types of time complexity?
The common types, from fastest to slowest growth, are constant O(1), logarithmic O(log n), linear O(n), linearithmic O(n log n), quadratic O(n²), cubic O(n³) and exponential O(2ⁿ). Array access is O(1), binary search is O(log n), merge sort is O(n log n) and naive recursive Fibonacci is exponential.
How do you calculate the time complexity of an algorithm?
Count how many times the basic operation runs as a function of n. Multiply for nested loops, add for sequential blocks, drop constants and keep only the dominant term. A loop that halves n each time is O(log n). For recursive code, write a recurrence such as T(n) = 2T(n/2) + n and solve it with a recursion tree or the Master theorem.
What is the difference between time complexity and space complexity?
Time complexity measures how the number of operations grows with input size. Space complexity measures how much extra memory the algorithm needs as input grows. Merge sort, for example, takes O(n log n) time and O(n) extra space, while heap sort takes O(n log n) time with only O(1) extra space.
Is Big O notation the same as worst-case complexity?
No. Big O is an upper bound on how a function grows, while worst case describes the input that makes an algorithm slowest. You can give a Big-O, Omega or Theta bound for the best, average or worst case. Big O is commonly quoted for the worst case because it guarantees performance will never be slower.
Which data structure has the best time complexity for searching?
A hash table gives O(1) average-case search, which is the fastest for exact-key lookups, though its worst case is O(n). If you need sorted order or range queries, a balanced binary search tree such as an AVL or Red-Black tree gives a guaranteed O(log n) search.
