Search⌘ K
AI Features
Home
Courses
A Visual Introduction to Algorithms

Big-θ (Big-Theta) notation

Explore Big-Theta notation to understand how it precisely describes the asymptotic growth of an algorithm's running time. Learn to identify tight upper and lower bounds, ignoring constant factors and lower order terms, for clearer performance analysis.

We'll cover the following...

Let's look at a simple implementation of linear search (in the language of your choice):

JS
C++
Python
var doLinearSearch = function(array, targetValue) {
  for (var guess = 0; guess < array.length; guess++) {
    if (array[guess] === targetValue) { 
        return guess;  // found it!
    }
  }
  
  return -1;  // didn't find it
};

Let's denote the size of the array by nn. The maximum number of times that the for-loop can run is nn, and this worst case occurs when the value being searched for is not present in the array. Each time the for-loop iterates, it has to do several things: compare guess with nn; compare array[guess] with targetValue; possibly return the value of guess; and increment guess. Each of these little computations takes a constant amount of time each time it executes. If the for-loop iterates nn times, then the time for all nn iterations is c1⋅nc_1⋅n, where c1c_1 is the sum of the times for the computations in one loop iteration. Now, we cannot say here what the value of  ...