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

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

0 votes

*O*(*n*) time taken by an algorithm, how do you calculate it for a given algorithm.

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 x:=x+1;

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++ ) statement; }

It'd be O(*n*^{2}) because the statement will be executed *n*^{2} times for every *i*i.

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(log*n*) 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 3*n*+6. Hence, O(*n*).

- All categories
- Computer Science & Information Technology 452
- Mathematics 80
- Aptitude Questions 114
- GATE 94
- Online Aptitude Test 6
- Gate Exam 22
- Gate Syllabus 6
- Gate Preparation 35
- Gate Coaching 14
- Online Registration 20
- Electronics and Communication (EC) 0
- Electrical Engineering (EE) 3
- Civil Engineering (CE) 0
- Mechanical Engineering (ME) 2
- Aerospace Engineering (AE) 0
- Agricultural Engineering (AG) 0
- Architecture and Planning (AR) 0
- Biotechnology (BT) 0
- Chemical Engineering (CH) 1
- Chemistry (CY) 0
- Ecology and Evolution (EY) 0
- Geology and Geophysics (GG) 0
- Instrumentation Engineering (IN) 0
- Mining Engineering (MN) 0
- Petroleum Engineering (PE) 0
- Physics (PH) 0
- Production and Industrial Engineering (PI) 1
- Textile Engineering and Fibre Science (TF) 0
- Engineering Sciences 1
- Life Sciences 2
- Mathematics (MA) 0