I'm trying to compute the big-O time complexity of this selection sort implementation:

```
void selectionsort(int a[], int n)
{
int i, j, minimum, index;
for(i=0; i<(n-1); i++)
{
minimum=a[n-1];
index=(n-1);
for(j=i; j<(n-1); j++)
{
if(a[j]<minimum)
{
minimum=a[j];
index=j;
}
}
if (i != index)
{
a[index]=a[i];
a[i]=minimum;
}
}
}
```

How might I go about doing this?

Let's begin by looking at the inside of the outer loop. It does O(1) work with the initial assignments, then has a loop that runs n - i times, then does O(1) more work at the end to perform the swap. Therefore, the runtime is Θ(n - i).

If we sum up from i going from 0 up to n - 1, we get the following:

n + (n - 1) + (n - 2) + ... + 1

This famous sum works out to Θ(n^{2}), so the runtime would be Θ(n^{2}), matching the known runtime of this algorithm.

Hope this helps!

Formally, you can obtain the exact number of iterations with the order of growth using the methodology below:

Executing the following fragment code (synthetic version of the original code), `sum`

will equal the closed form of T(n).

```
sum = 0;
for( i = 0 ; i < ( n - 1 ) ; i ++ ) {
for( j = i ; j < ( n - 1 ) ; j ++ ) {
sum ++;
}
}
```

Similar Questions

Bubble sort and gnome sort, they have the same complexity on worst, best, and average cases. What is the difference between bubble sort and gnome sort (not their names...)?

I've been doing BigO recently, and I get the formula ok, but I've written a piece of code that takes and input and returns a time taken to complete a sort. So I have the input and time, how do I use t

Using framework's Random class I came up with following lazy implementation to shuffle a deck of card. I estimate worst case complexity of following code as O(N + NlogN). Am I right? DataStructures en

I have the below merge sort iterative implementation, but somehow, it is not working. I debugged it, but couldn't find the cause. Merge'ing function would remain the same as the recursive case, only t

I am curious about why bucket sort has a runtime of O(n + k) if we use buckets implemented with linked lists. For example, suppose that we have this input: n = no of element= 8 k = range = 3 array = 2

Is it possible to write a compile time recursive sort function in c++ using the selection algorithm? I want to sort array x from element istart to element iend in ascending order. Array x has N elemen

I was asked to make a selection sort algorithm, but it's not working and I don't know why. Here's the code: int count = 0; int count2; int min; int size = scan.nextInt(); int temp = 0; int[] numbers

This may seem like a simple question but when I attempted to implement selection sort in Python, I do not get a sorted list. Is there something wrong with my implementation? The subsetting may be a pr

I need to sort an array of float values into another array using only pointers. In this function, I've already entered all the values into the pointer array p_data_start. The code to sort is after all

I've implemented insertion sort in C(Visual Studio) and Java(Eclipse) to analyse the time required for completion and to compare the difference in both the languages. I tried to find out the worst cas

Is there any Python complexity reference? In cppreference, for example, for many functions (such as std::array::size or std::array::fill) there's a complexity section which describes their running com

We have two sets A, B and we want to compute set difference A - B, we will sort first elements of B with quicksort which have average complexity O(n * log n) and after we search each element from A in

i have a selection sort algorithm that partially works, i am using it to sort an array of class objects by age when it does this it sorts some of the contents correctly but fails to sort the first ele

How does selection sort work with strings? I've done some searching and can't seem to find a definitive answer. If I had 4 names [Rob, Adam, Tom, Thomas] - how would a selection sort, sort these? Woul

so I am implementing quick sort and I get an error once I start the program. I think that logic-wise everything should be okay. I think that the problem is within the swap function since it doesn't cr

In the book programming interviews exposed it says, the complexity of the program below is O(N), but I dont understand how this is possible. Can someone explain ? int var= 2; for (int i=0 ; i<N ; i

I have an equation the uses the inclusion-exclusion principle to calculate the probabilities of correlated events by removing the duplicate counting of intersections. Now I want to know the complexity

I'm attempting to implement a merge sort in Java for my Algorithms class. I've tried several approaches, including assigning the last array indices in both arrays as infinity using Java's Double.POS

I implemented merge-sort in python import sys def mergeSort(array): if len(array) < 2: return array middle = len(array) / 2 left = mergeSort(array[:middle]) right = mergeSort(array[middle:]) return

From Sonar Metrics complexity page the following method has a complexity of 5. public void process(Car myCar){ <- +1 if(myCar.isNotMine()){ <- +1 return; <- +1 } car.paint(red); car.change

I like Textmate's Sort Lines in Selection feature a lot. Is there something similar for Xcode 4? If not, what would be the best way to integrate such a feature (a plugin, Applescript, ...)?

I have a table a with two fields, say value1 and value2. Every single selection I will then make on this table is sorted on value2 DESC, but since the table is rather large I can't do it vanilla any

I am a newbie in Java and OOP, the previous language that I've learned being C. I am trying to create a Linked List that extends AbstractList and that allows the usage of Collections.sort() function.

I need to sort a List of Job which I currently do with: List<Job> jobs = new ArrayList<Job>(); Job job0 = new Job(a, 1, Arrays.asList(t0)); Job job1 = new Job(a, 2, Arrays.asList(t0

I'm trying to run selection sort in python, this is the code that I'm using def main(list): input_array = [12, 9, 13, 7, 3, 19, 6, 5] output_array = selection_sort(input_array) print(output_array) def

I am having trouble with trying to implement the merge sort algorithm. I would appreciate it if someone can help me out. Here is what I have. #include <iostream> #include <deque> using siz

INSERTION_SORT (A) FOR j ← 2 TO length[A] //c1*n key ← A[j] //c2*(n-1) i ← j − 1 //c3*(n-1) WHILE i > 0 and A[i] > key //c4*sigma(j=2 to n)of(tj) A[i +1] ← A[i] //c5*sigma(j=2 to n)of(tj-1) i ←

I've implemented a version of quicksort in C#, and performed some quick benchmarks to compare against the C# List<T>.Sort. I have found my implementation to be significantly slower than the libr

I am trying to run selection sort to see how it work and apparently, the code that I have doesnt work as expected, can someone help me point out what i did wrong? I know the thing goes wrong at swappi

In heap sort, if all the elements are only 0s and 1s, will the complexity change compared to the normal case with random elements?

Hi I have two algorithms that need their complexity worked out, i've had a try myself at first; O(N^2) & O(N^3) Here they are: Treat Y as though it's declared 'y=int[N][N]' and B as though 'B=int[

I'm making a program in c# and I got a list with objects which I want to sort with c#. I can't get it working nor do I understand how it should be implemented. I did some research for which algorithm

I keep getting this debug error that my data is corrupted. I don't know how that is possible nor do I know how to fix it. This program populates a array then uses a selection sort type algorithm to

I wonder if there are any common or best practice techniques out there if one needs to find the complexity of algorithms?

I did this sort function in C++ for Linked List void sort() { node* ctr; node* innerctr; info temp; node* max; ctr = start; while(ctr!=NULL) { innerctr=ctr->next; max=ctr; while(innerctr!=NULL) { i

I read in some text they have mentioned that Heap Sort has the best case complexity as Ω(n), O(n log n). Which means time complexity of heap sort depends on I/P permutation. but I don't think I/p perm

I am trying to determine why the bigO of this algorithm is m^2*n, and why the innermost loop is executing in m^2*n steps. int m=10, n=15; int inLoop = 0, midLoop = 0, outLoop = 0; for(int i=1;i<=

I need a treeview in .net with supported multi selection. A own implementation in wpf or winforms ( this two don't have multi selection out of the box !? ) is a no go, i need the multi selection visib

What is a good implementation for calculating the gradient in a n-layered neural network? Weight layers: First layer weights: (n_inputs+1, n_units_layer)-matrix Hidden layer w

I am reviewing implementations for some basic data structures and the algorithms operating on them. I guess the idiomatic F# code for Insertion Sort is very much like: let rec insert x = function | [

How the complexity of an algorithm involved with combinatorial operations is classified. Let's say the input is m, n, and the complexity is determined by C(m,n). (C is the combination function of cho

What is the time complexity of the implementation of a binary tree traversal below? void Tree::nonRecInOrder() { // nonrecursive inOrder Traversal using Stack Stack< TreeNode* > s ; // declare a

In a typical dynamic array implementation, we double the stack when there is no room for a new element. In this case of doubling the average time for push operation is O(n). What is the complexity of

When i compile and run this selection sort of random char array i get a Segmentation fault (core dumped) error. I think it's got to do with accessing unallocated memory in my selection sort section. C

There is an array related problem, the requirement is that time complexity is O(n) and space complexity is O(1). If I use Arrays.sort(arr), and use a for loop to one pass loop, for example: public sta

I want to implement bubble sort as the second option to sort the TXT file. Any solution would be highly appreciated. Here is what i have done so far. I have been able to in initialize selection sort p

I'm trying to create a simple(?) selection sort program in C that selects the largest integer of an integer array and places it in the location a[n-1], places the second largest number in a[n-2], etc

I am attempting to implement a selection sort of an array in NASM that runs on 64-bit Linux. The array is declared as: section .bss strbuf resb 10 small resb 1 ; current minimum value The sort algori

I am working on some sort algorithms for a school project and i have a problem . The following code its not sorting the array,I have tried the same code with array of numbers(the only change is in the

There's a part of the selection sort algorithm that I don't understand. In the latter part of the code (where the temp variable is used, why are L[i] and L[minIndx] assigned values? Aren't those value