Order Of Execution Time Function For An Algorithm
TECTechnics Classroom   TECTechnics Overview

Order Of Execution Time Function For An Algorithm

Suppose the execution time function for an algorithm is:
f(x) = 3 + 8x + x2
Determine the order of f(x).

The strings: S7P5A51 (Physical - Change).

The math:
Pj Problem of Interest is of type change (physical - change). Problems of time are change problems.

An algorithm is the totality of the steps necessary to solve a given problem. In the context of machine computing, an algorithm consists of the instructions a machine uses to solve a given problem. The execution time of an algorithm measures the time it takes to execute an algorithm for a given set of data.

The execution time function f(N) for an algorithm is of order g(N) if there exists a positive number K and an integer Q such that:
f(N) ≤ K[g(N)] for all N ≥ Q ---------------(1)

So, if f(x) = 3 + 8x + x2
Then for x ≥ 8, f(x) = 3 + 8x + x2 ≤ x2 + x2 + x2 = 3x2.
So, f(x) ≤ 3x2 for all x ≥ 8 satifies equation (1)
So, the given execution time function is of order x2.

The following are common orders of execution time function for an algorithm:
constant k (constant execution time)
log2N (logarithmic execution time)
N (linear execution time)
N log2N
N2 (quadratic execution time)
N3 (cubic execution time)
XN (exponential execution time)

Constant execution time being the best and exponential execution time being the worst.

Blessed are they that have not seen, and yet have believed. John 20:29

TECTechnic Logo, Kimberlee J. Benart | © 2000-2021 | All rights reserved | Founder and Site Programmer, Peter O. Sagay.