Search⌘ K
AI Features
Home
Courses
Data Structures & Algorithms In Go

Deriving an Algorithm's Runtime Function

Explore how to derive an algorithm’s runtime function by examining the number of operations and their relationship to input size. Understand time complexities of constants, loops, nested loops, if-else branches, and logarithmic processes. This lesson helps you break down code execution steps to estimate algorithm efficiency in Go.

We'll cover the following...

Runtime function of an algorithm

The number of operations performed determines how long an algorithm takes to run for a given input. An algorithm’s running time increases as the number of operations increases and vice versa. We normally want to know how many operations an algorithm will perform. The following are some derivations of runtime functions of algorithms:

Constants

If any line of code is a statement with basic operations, e.g., comparisons, assignments, or reading a variable, they take constant time. Thus, the time complexity of each statement is O(1)O(1).

Let’s look at an example.

Go (1.6.2)
i := 0 //statement1
j := i + 1 //statement2
k := i + j //statement3

Now, let’s calculate the time complexity of the example above.

Total time complexity = time(statement1) + time(statement2) + time(statement3)

If each given statement executes basic operations, the time complexity of each statement is O(1)O(1).

 ...