CODEWITHSUNDEEP
algorithmmaxtime-complexity
Notyourthing
Notyourthing

Reputation: 19

Linear complexity of algorithms explanation

So I came across this paragraph in my book :

The Algorithm arrayMax, for computing the maximum element in an array of n integers, runs in O(n) time.

Justification: The number of primitive operations executed by algorithm array- Max in each iteration is a constant. Hence, since each primitive operation runs in constant time, we can say that the running time of algorithm arrayMax on an input of size n is at most a constant times n, that is, we may conclude that the running time of algorithm arrayMax is O(n).

The part that I dont understand is "..the running time of algorithm arrayMax on an input of size n is at most a constant times n..."

What does " a constant times n " mean?

Upvotes: 1

Views: 139

Answers (1)

David Hunsicker
David Hunsicker

Reputation: 1240

A constant, in this context, is indicating that it is a finite understandable whole number, an integer.

For purposes of 'a constant times n' this would mean that each iteration of an operation, may be 5, 10, 15, etc operations, and n, being the number of times the application will perform this operation, hence, the O(constant*n)

The number of operations needed to perform the task doesn't change, however the scale of the program can have up to n objects.

Upvotes: 2

Related Questions