GATE Exam | Aptitude Questions | GATE Syllabus | GATE Result | Mock Test | GATE Preparation
0 votes

big-O notations like O(n)  time taken by an algorithm, how do you calculate it for a given algorithm.

asked in Computer Science by anonymous

1 Answer

0 votes

Big O notation ignores all constant factors so that you're left with an upper bound on growth rate.

For a single line statement like assignment, where the running time is independent of the input size n, the time complexity would be O(1):

int index = 5;  *//constant time*   
int item = list[index]; *//constant time*

For a loop like:

for i:=1 to n do  

The running time would be O(n), because the line x=x+1 will be executed n times.

But for:

for ( i = 0; i < N; i++ ) {  
  for ( j = 0; j < N; j++ )  

It'd be O(n2) because the statement will be executed n2 times for every ii.

For a while statement, it depends on the condition and the statement which will be executed in it.

i := 1;
while ( i < n )  
  i = i * 2;

The running time is logarithmic, O(logn) because of the multiplication by 2.

For instance:

Double test(int n){  
  int sum=0;  -> 1 time
  int i;  -> 0 time
  for(i=0; i<=n;i++)  -> n+2 times
    scanf("%d",&a);  -> n+1 times
    sum=sum+a;  -> n+1 times
  return sum;  -> 1 time

Which is 3n+6. Hence, O(n).

answered by anonymous

Related questions

The best answer to any question