Algorithm complexity — asymptotic analysis

Big-O and the amount of time

int x = 10 * n;
//or
if(x < 10)...
public static int BinarySearch(int[] inputArray, int targetValue)
{
int min = 0;
int max = inputArray.Length - 1;
int guess; while (min <= max)
{
guess = (min + max) / 2; if (targetValue == inputArray[guess])
{
return guess;
}
else if (targetValue < inputArray[guess])
{
max = guess - 1;
}
else
{
min = guess + 1;
}
} return -1;
}
public static int UnsortedSearch(int[] inputArray, int targetValue)
{
for (int i = 0; i < inputArray.Length; i++)
{
if(inputArray[i] == targetValue)
{
return i;
}
} return -1;
}
class HeapSort
{
public static void Sort(int[] elements)
{
BuildHeap(elements);

for (int swapToPos = elements.Length - 1; swapToPos > 0; swapToPos--)
{
ArraySwap(elements, 0, swapToPos);

Heapify(elements, swapToPos, 0);
}
}

private static void BuildHeap(int[] elements)
{
int lastParentNode = elements.Length / 2 - 1;

for (int i = lastParentNode; i >= 0; i--)
{
Heapify(elements, elements.Length, i);
}
}

private static void Heapify(int[] heap, int length, int parentPos)
{
while (true)
{
int leftChildPos = parentPos * 2 + 1;
int rightChildPos = parentPos * 2 + 2;

int largestPos = parentPos;

if (leftChildPos < length && heap[leftChildPos] > heap[largestPos])
{
largestPos = leftChildPos;
}

if (rightChildPos < length && heap[rightChildPos] > heap[largestPos])
{
largestPos = rightChildPos;
}

if (largestPos == parentPos)
{
break;
}

ArraySwap(heap, parentPos, largestPos);

parentPos = largestPos;
}
}

private static void ArraySwap(int[] vet, int offset1, int offset2)
{
int tmp = vet[offset1];
vet[offset1] = vet[offset2];
vet[offset2] = tmp;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
//operations
}
}
class Subsets
{
public static List<decimal[]> Create(decimal[] values)
{
var result = new List<decimal[]>();
var subset = new Stack<decimal>();
int idx = 0;

Seek(values, result, subset, idx);

return result;
}

private static void Seek(decimal[] values, List<decimal[]> result, Stack<decimal> subset, int index)
{
if(subset.Count > 0) result.Add(subset.ToArray());

for (int i = index; i < values.Length; i++)
{
subset.Push(values[i]);

Seek(values, result, subset, i + 1);

subset.Pop();
}
}
}

Conclusion

--

--

--

Software Performance Engineer wannabe

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Glauber Cini

Glauber Cini

Software Performance Engineer wannabe

More from Medium

An Introduction to Functions in Heap

SimpleDB: A Basic RDBMS Built From Scratch

Introduction To ML.NET (Hands-On Machine Learning with ML.NET) | Part 1

Merge and Unmerge Excel Cells in Java