Mark As Completed Discussion

Algorithm Complexity and Big O Notation

Objective: In this lesson, we'll cover the topics of Algorithm Complexity and Big O Notation. By the end, you should:

  • Be familiar with these terms and what they mean.
  • See their use in practice.
  • Use these tools to measure how "good" an algorithm is.

In software engineering, developers can write a program in several ways.

For instance, there are many ways to search an item within a data structure. You can use linear search, binary search, jump search, interpolation search, among many other options.

Our focus in this lesson is on mastering Algorithm Complexity and Big O Notation. But what we want to do with this knowledge is to improve the performance of a software application. This is why it's important to understand which algorithm to use, depending upon the problem at hand.

Let's start with basics. A computer algorithm is a series of steps the machine takes in order to take an input and compute an output. There are several ways to measure its performance. One of the metrics used to compare algorithms is using this notion of algorithm complexity.

Sounds challenging, doesn't it? Don't worry, we'll break it down.

Introduction

Algorithm complexity can be further divided into two types: time complexity and space complexity. Let's briefly touch on these two:

  • The time complexity, as the name suggests, refers to the time taken by the algorithm to complete its execution.
  • The space complexity refers to the memory occupied by the algorithm.

In this lesson, we will study time and space complexity with the help of many examples. Before we jump in, let’s see an example of why it is important to measure algorithm complexity.