Hi..
Can you please explain how to calculate the time complexity for the code given below..

int flag,temp;

do {

flag=0;

for(int j=0;j<n;j++) {

if((j+1)==n)
continue;

if(a[j]>a[j+1]){

flag=1;
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}while(flag==1);

2
Contributors
1
2
Views
6 Years
Discussion Span
Last Post by Rashakil Fol

Certainly. Certain inputs to your algorithm affect the behavior of the code's running time. An upper bound on the running time can usually be expressed by some measurement of the size of the input, either by the value itself or the number of elements or whatever. Suppose you have one such input and its size is n.

Then figure out some function A(n) which describes an upper bound for the number of "operations" the algorithm would take when the input is of size n. That's where an "operation" is a primitive operation that takes a CPU a bounded amount of time, such as adding two fixed-width integers or reading and writing from memory.

Then take the function A and figure out a simple function f of the same complexity, i.e. so that we can say there's three positive numbers C and D and n_0 such that D f(n) <= A(n) <= C f(n) for all n greater than n_0. For example if A(n) = log10(n) + 5, we might pick f(n) = log(n).

Then we can say that the running time of the algorithm is O(f(n)).

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.