How To Calculate Complexity?

Question

I am a beginner in algorithms and I don't know how to calculate complexity.

Example:
int x=10,y;
y = x;

What is the complexity in example above?

Thanks

With respect to which variable? I suggest that getting a textbook is a better way to learn this than posting questions on StackOverflow. — Peter Taylor, Feb 11 '11 at 11:56

score 2 · Answer 1 · answered Feb 11 '11 at 11:57

2

That should be O(1) if you refer to the O-Notation.

answered Feb 11 '11 at 11:57

imbaer

554
3
21

score 2 · Answer 2 · edited May 23 '17 at 10:24

In the Big O Notation this corresponds to O(1) which basically means that the run-time of the operation is constant or at least is less than a certain constant. Ergo, the run-time does not depend on the input you have. As you may infer from what I wrote, the Big O Notation only gives an upper bound of the operation. There is also other notations which give a lower-bound and so on.

An example of a case where it does depend on the input could be:

int res = 0;
int[] arr = getSomeArray();
foreach (int i in arr)
    res = res + i;

Here the run-time depends on how big the array is, and if we give the length of the array the variable n then this will be O(n). Again, the Big O Notation does not specify exactly how long it will take to execute but, in this case, just says that we can multiply n by some constant and then it will be finished within n*some s.

A more detailed explanation is given here: What is a plain English explanation of "Big O" notation?

How To Calculate Complexity?

2 Answers2