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

The blog does not intend to maintain this theoretical bias, but rather to try to bring technological problems faced in a real way.

--

--

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