Time complexity
= Time complexity
{title2=$T(n)$}
{wiki}
The time complexity of an <algorithm> bounds its number of computation steps as a function of its input length.
Specify both the size parameter and the operations counted. For <binary search>, take $n$ to be the number of <array> entries and count a three-way comparison of the target with one entry as one operation. Code using separate equality and less-than tests may perform two primitive tests per inspected entry; this changes a constant factor. The <input> size in bits is a different parameter when entries have variable-length representations.
Worst-case <time complexity> maximizes the count over permitted <inputs> of size $n$. An absent target forces $n$ comparisons in <linear search>. For <binary search>, the worst-case count is $\lfloor\log_2 n\rfloor+1$ for $n\geq1$, attained by a target larger than every entry. Both have a best case of one comparison when the first inspected entry matches.
In <Big O notation>, the worst-case bounds are $O(n)$ and $O(\log n)$ respectively. Here $T(n)=O(g(n))$ means that fixed constants $C,n_0$ exist with $T(n)\leq Cg(n)$ for all $n\geq n_0$. It is an upper bound, so a logarithmic count is also $O(n)$; the sharper bound communicates its scaling better. The base of the <logarithm> changes only a constant factor.
For $n=1{,}000{,}000$, <linear search> can require $1{,}000{,}000$ comparisons, whereas <binary search> needs at most $20$, since $2^{19}\leq n<2^{20}$. Doubling $n$ adds just one to the worst-case <binary search> count. These are operation counts, not measured machine runtimes. Translating them into logarithmic execution time assumes constant-cost indexed access, comparison and index arithmetic. Long entries can make comparison expensive; a <linked list> does not provide constant-cost access to an arbitrary middle index. Building or sorting the <array> is additional work: <merge sort> can provide order for many subsequent searches, but its cost belongs in the analysis too.