analysing time complexity of my programs

问题:

I have problem in determining time complexities of algorithms.

for(int i=0;i <n i++){}   O(n)

for(int i= 0 ;i<n ;i++){    O(n^2)
  for(int j=0;j<n;j++){ 

  }
}

Now for following code whats the complexity

for(i =0; i<n ; i++) {}
for (j=0;j<n ;j++ ) {} 

is it O(2n) as it invloves 2 seperate loops?

what if i start j =5 to n?

回答1:

There is no O(2n), it's just O(n). In other words, it scales at the same rate as n increases.

If it was a nested loop, it would be O(n2) but the presence of your {} empty blocks means it isn't nested.

And it makes no difference whether you start at one or five, it still scales with n, just with a slightly negative constant addition. Hence still O(n).

The complexities O(n), O(cn) and O(n+c) (where c is a constant) are all equivalent. In addition, you also generally only use the term with the highest effect.

So you won't usually see O(7n3 + 3n2 + 12n + 2), that will be simplified to O(n3).

回答2:

There is no such thing as O(2n). Time complexity refers to how an algorithm scales to infinity, not to its actual running time. In your examples, you have two loops that are both linear [ O(n) ] time, meaning that they will scale linearly with the input, hence your overall algorithm is O(n).

If you start j=5, it's still O(n) because it still scales linearly.

So in essence, O(2n) == O(n).

回答3:

The end result is that through some fancy math that I cannot remember, you are able to turn things like 2n into just big O(n). The coefficients are considered constants because we are concerned with the complexity and when dealing with that issue alone, you need to examine the part of an equation that causes the most growth. In this case, Big O(n^2) is the most predominate element within the complexity of the equation. Therefore, your algorithm is considered to be Big O(n).

my apologies, small typo based on misreading the last lines of code. The one you asked about would be Big O(n)

回答4:

There are two important rules of Time complexity which applies if and only if the value of n is very large...

1. The coeffeicient of the higher order term can be neglected.

2. All lower order terms can be igonred.

Why these assumptions are quite simple, let`s consider an example:-

Suppose the time complexity is 5n^2 + 3n . At very low values of n, the coefficient and the lower order terms gets prominent for a small change in n. But suppose if the value of n is very large, the effect of the lower order term on the time complexity is very less and moreover the coefficient of the highest order term can also be ignored in the same way.

Note time complexity plays a major role only when n approaches infinity theoritically.

回答5:

Yes, it's O(2n), but that is the same as O(n), because multiplying by a constant does not matter in asymptotic complexity. Similarly, if you skip the five first elements, your loop takes O(n-5) time, but that too is the same as O(n), because adding or subtracting a constant is even weaker than multiplying by a constant. See e.g. http://en.wikipedia.org/wiki/Big_O_notation for the definitions.

回答6:

Complexity is measurement for shape of function that describes relation input n and time .

Keep in mind that there is no constant becuase in most cases you do not know constant. You might use constant if you compare two comparable algorhitms, but in most cases you would cite generic complexity and measure time whit some input n. In your case case O(2*n) is same as 2*O(n) and this is just O(n) since 2*O(n) does not say much as is and can be compared using constant 2 only whit previous algorithm. Saying that second algorithm has complexity 2*O(n) does not have not much sense.

Look on complexity in this way.

Lets say that you have algorithm that takes n = one million. What is approximate size or order of number of operations

O(n)            -> 1e6   and this can be calculated in most cases  
O(n * log(n))   -> 2*1e7 this can also be calculated in reasonable time.
O(n^2)          -> 1e12  you will not be able to compute whit this algorithm in reasonable time
O(n^3)          -> 1e18  here are so many operations that you have to think twice on how you are going to aproach this problem