# Algorithm - Complexity.

• 05-12-2003
visitant...
Algorithm - Complexity.
Hello, I'm reading a little bit about complexity in a book about algorithms. The book says that the complexity of the algorithm is calculated by the number of operations that we do in the algorithm. Example:
Code:

```void swap(int *x, int *y) {     int tmp = *x;         *x = *y;     *y = tmp; }```
We do here 3 steps(operations) to swap the values, but he still says that the algorithm is O(1) and not O(3). Why is O(1) if we still make 3 steps to get the result?
• 05-12-2003
zdude
No idea.

I don't think there really is a way to rate algorithmic complexity.

In ASM that would be more commands, and in machine code even more.
• 05-12-2003
Draco
I think you may be confused with what your book is telling you. I have a book that talks a little about algorithm complexity (yes, a way to rate it does exist zdude, google it). In my book, a linear algorithm like the one you posted has a complexity of O(n) where n is the number of data items that the algorithm will be applied to, not the number of code lines in the algorithm.
• 05-12-2003
samps005
when talking about algorithm complexity, you usually do not bother multiplying the complexity by constants.

That program is O(1) because it takes a constant amount of time to do the calculation.

An algorithm is O(n) if the size of the input can vary and the time it takes to complete the algorithm is linear in respect to the size of the input.

say you have this code where n is the size of the list

Code:

```int main(n, list){   int x = 0;   int p = 0;   for (i = 0; i <= n; i++){       list(i) = p;       x = x + p;   } }```
this function runs n times and does 2 operations per time.
so the run time is 2n, but in big O notation you don't need to mention the constant 2, only the order of growth. So it is O(n).
• 05-12-2003
visitant...
I'm starting to understand a little bit, I found some rules in my book like:
Code:

```O(ConstantNumber) = O(1); O(n*(ConstantNumber)) = (ConstantNumber) * O(n) = O(n);```
With this in mind is easier to understand the problem. thanks for the help.
• 05-13-2003
Magos
The big-O notation O(n) is basically defined as a constant multiplied by n: A * n.

If you have O(3), that is 3 * A * 1.
3 * A is another constant B, so the expression is B * 1 which is O(1).