Time Complexity Problem (1 Viewer)

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

1. The problem statement, all variables and given/known data

Compute the time complexity of the following sorting algorithm on an array L[0..n-1] in terms of n. Basic Operation only includes comparison and swap.
sort (L, n)
{
int i=0, j;
while(i<n-1){
s = i ;
j=i+1;
while(j<n){
if (L[j]<L) s = j;
j++;
}
swap (L,L);
i++;
}
}


2. Relevant equations

N/A

3. The attempt at a solution
Well, we have just studied about the big O notation last week, but I have no idea how we apply it to solve this kind of problem.
 
It looks to me like n^2 because of the nested loops.
 
It looks to me like n^2 because of the nested loops.
Thank you, I think it x2 because of 2 loops, and each loop is executed n times.
 
Yes n^2. The inner loop has a worst case of n and the outter loop also runs n times.
 

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top