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

Deriving an Algorithm's Runtime Function

Explore how to calculate the runtime function of algorithms by analyzing operations like constants, loops, nested loops, if-else statements, and logarithmic reductions. Understand the principles behind time complexity to evaluate algorithm efficiency effectively.

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

Total time complexity = O(1) + O(1) + O(1)

Hence, the total time complexity is ...