Question: When estimating the time complexity of a certain algorithm, let's say the following in pseudo code:

```
for (int i=0; i<n; i++) ---> O(n)
  //comparison? ---> ?
  //substitution ---> ?
 for (int i=0; i<n; i++) ---> O(n)
  //some function which is not recursive

```

In this case the time complexity of these instructions is `O(n)` because we iterate over the input `n`, but how about the comparison and substitution operations are they constant time since they don't depend on `n`?

Thanks

Answer: 
Both of the other answers assume you are comparing some sort of fixed-size data type, such as 32-bit integers, doubles, or characters. If you are using operators like `<` in a language such as Java where they can only be used on fixed-size data types, and cannot be overloaded, then that is correct. But your question is not language-specific, and you also did not say you are comparing using such operators.

In general, the time complexity of a comparison operation depends on the data type you are comparing. It takes O(1) time to compare 64-bit integers, doubles, or characters, for example. But as a counter-example comparing strings in lexicographic order takes O(min(*k*, *k'*)) time in the worst case, where *k*, *k'* are the lengths of the strings.

For example, here is the Java source code for the [`String.compareTo`](http://hg.openjdk.java.net/jdk7u/jdk7u6/jdk/file/8c2c5d63a17e/src/share/classes/java/lang/String.java) method in OpenJDK 7, which clearly does not take constant time:

```java
    public int compareTo(String anotherString) {
        int len1 = value.length;
        int len2 = anotherString.value.length;
        int lim = Math.min(len1, len2);
        char v1[] = value;
        char v2[] = anotherString.value;

        int k = 0;
        while (k < lim) {
            char c1 = v1[k];
            char c2 = v2[k];
            if (c1 != c2) {
                return c1 - c2;
            }
            k++;
        }
        return len1 - len2;
    }

```

Therefore when analysing the time complexity of comparison-based sorting algorithms, we often analyse their complexity *in terms of* the number of comparisons and substitutions, rather than the number of basic operations; for example, [selection sort](https://en.wikipedia.org/wiki/Selection_sort) does O(*n*) substitutions and O(*n*²) comparisons, whereas [merge sort](https://en.wikipedia.org/wiki/Merge_sort) does O(*n* log *n*) substitutions and O(*n* log *n*) comparisons.
> 
> but how about the comparison and substitution operations are they
>  constant time since they don't depend on n?
> 
> 
> 

**Yes**. Comparison and substitution operations are a constant factor because their execution time doesn't depend on a size of the input. Their execution time takes time but, again, it's independent from the input size.

However, the execution time of your `for` loop grows proportionally to the number of items `n` and so its time complexity is `O(n)`.

**UPDATE**

As @kaya3 correctly pointed out, we assume that we deal with fixed-size data types. If they're not then check an answer from @kaya3.