Search⌘ K
Home
Courses
A Visual Introduction to Algorithms

Big-θ (Big-Theta) notation

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 c1c_1 is, because it depends on the speed of the computer, the programming language used, the compiler or interpreter that translates the source program into runnable code, and other factors. This code has a little bit of extra overhead, for setting up the for-loop (including initializing guess to 00) and possibly returning -1 at the end. Let's call the time for this overhead c2c^2, which is also a constant. Therefore, the total time for linear search in the worst case is  ...