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: 
First, read [this](http://kddlab.zjgsu.edu.cn:7200/students/lipengcheng/%E7%AE%97%E6%B3%95%E5%AF%BC%E8%AE%BA%EF%BC%88%E8%8B%B1%E6%96%87%E7%AC%AC%E4%B8%89%E7%89%88%EF%BC%89.pdf) book. Here is good explanation of this topic.

1. Comparsion. For instance, we have two variables **a** and **b**. And when we doing this `a==b`we just take **a** and **b** from the memory and compare them. Let's define "*c*" as cost of memory, and "*t*" as cost of time. In this case we're using *2c* (because we're using two cells of the memory) and *1t* (because there is only one operation with the constant cost), therefore the *1t* - is the constan. Thus the time complexity is constant.
2. Substitution. It's pretty same as the previous operation. We're using two variables and one operation. This operation is same for the any type, therefore the cost of the time of the substitutin is constant. Then complexity is constant too.
> 
> 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.