What unit of time does the variable n refer to if an algorithm has O (n) time complexity?

Input size.

Explanation:

When we measure the time complexity of an algorithm we always find it in big-oh notation like O (n). The n always represents the input size.

Suppose the size of an array is 64 and we have to find an element in this array using binary search and linear. As we know the worst case time complexity of the binary search is O (logn).

t (n) = O (log64)

t (n) = O (6).

So the loop will run maximum of 6 times.

The worst case time complexity of linear search is O (n).

t (n) = O (n)

t (n) = O (64).

So the loop will run maximum of 64 times.

In both the cases n is the size of the array.