Member Avatar for Pnlakshmicse

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 Reply
  • 77 Views
  • 3 Days Discussion Span
  • Latest Post Latest Post by Rashakil Fol
Member Avatar for 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)).

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.