Functions or Programs with Linear Time Complexity ( O(N) complexity ) needs amount of time that directly propotional to the number of input elements.

For example, you want to write a function that returns the largest number from the unsorted array of integers. Program needs input of an integer array.

To solve this problem, lets implement it in following way:

Iterate over the array.

Assume the highest number X is the first number.

As you iterate to the next element, compare the highest number X with the current element. If current element is higher than X, current element will become X. If it is smaller than X, dont do anything. By that way, when you finish iteration, you will know the value of highest element.

In the above example, function exection time depends on number of elements in array. It iterates over all elements in the array, does comparison and returns the resuslt. It does matter if function get array of 10 integer or 1 million integers.

If it need to find highest element from 10 integers and takes x milliseconds to execute the function, it will need 10x milliseconds to find highest number from the array of 100 element. Hence running time of the algorithm is in direct proportion to the number of elements. Hence we can say that running time of this function is linear. This function can be represented with O(N) time or linear time complexity.

Java is a trademark of Oracle.

Apekshit.com is just for learning and testing. To improve basic understanding we provide some examples. We are constantly reviewing it to avoid errors, but we cannot warrant full correctness of all content.