Notes

[Notes Index] Trude’s Guide to Computer Science

Time Complexity The amount of steps required for an algorithm to execute. Big O Notation Maximum time for n input size. (Upper bound - worst case) Omega Notation Minimum time for n input size. (Lower bound) Ω(n²) Ω(n log n) Ω(n) Ω(log n) Ω(1) If both are the same, use θ Searching Algorithms Algorithm Average Time Complexity RAM Linear Search O(n) | Ω(1) 0 Binary Search O(log n) | Ω(1) 0 Linear Search Check every element until n is found. ...

From diodes and transistors, to a Turing complete computer.

The C Programming Language

Cast Strings to Numbers The atoi() function in stdlib is implemented similarly to the one below. ASCII encodes numbers in order, after special characters. The encoded value for '0' is 48, so subtracting any numeric char by 48 outputs its real numerical value. char number = '7'; int result = number - 48; int same_result = number - '0'; Algorithm to convert strings to numbers: int str_to_int(char *str) { int result = 0; for (int i = 0; str[i] != '\0'; i++) { if (str[i] < '0' && str[1] > '9') return -1; // Error if NaN result = (result * 10) + (str[i] - '0'); return result; } (result * 10) is shifting the previous number to the left, as it is an order of magnitude above the following digit. ...