A Visual Introduction to Algorithms/

...

/

Big-θ (Big-Theta) notation

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):

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 ...

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy