Geek Answers Handbook

Analysis of the time complexity of my programs

I have a problem in determining the time complexity of the 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 the next code, what a challenge

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

is it O (2n) as it causes 2 separate loops?

what if i ran j = 5 to n?

+5
source share
6 answers

No O(2n), it's that simple O(n). In other words, it scales at the same speed as n.

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

, , n, . , O(n).

O(n), O(cn) O(n+c) ( c - ) . , .

, O(7n3 + 3n2 + 12n + 2), O(n3).

+8

, - , , , 2n, O (n). , , , . Big O (n ^ 2) . Big O (n).

, , . , , Big O (n)

+1

, O (2n). , , . , [O (n)] , , , O (n).

j = 5, O (n), - .

, , O (2n) == O (n).

+1

, , n ...

  • .

  • .

, : -

, 5n ^ 2 + 3n. n n. , n , , , , .

. , n .

+1

, O (2n), , O (n), . , , O (n-5), , O (n), , . . http://en.wikipedia.org/wiki/Big_O_notation .

0

- , n .

, , . , , n. O (2 * n) 2 * O (n), O (n), 2 * O (n) , , 2 . , 2 * O (n), .

.

, , n = . .

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
0

More articles:


All Articles