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. ...
Binary Binary is a base-2 numeral system: A simple way to represent numbers using only two states. Binary Decimal Hexadecimal 0000 00 00 0001 01 01 0010 02 02 0011 03 03 0100 04 04 0101 05 05 0110 06 06 0111 07 07 1000 08 08 1001 09 09 1010 10 0A 1011 11 0B 1100 12 0C 1101 13 0D 1110 14 0E 1111 15 0F ...
Tools indent (format code) gcc / clang (compile code) man <function> (see function documentation) tldr <command> (quick command usage examples) valgrind (Look for memory leaks) valgrind —tool=massif (check a program’s RAM usage) View the output with Massif-Visualizer gdb (debugger) gdb —args <program> (if the program has command line args) Type run to start debugging, and backtrace for error details. file Check file information and, if it is an executable, compilation details. perf stat -r 10 -d <program> Benchmark a program. Data Types and Variables The binary length of each data type depends on the CPU, OS, and compiler, but in general, they follow the C specifications. To check the exact values for your platform, see limits.h. ...
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. ...
Convert C code into machine code in 4 steps: Preprocessing (Convert all preprocessor instructions: #…) Compiling (Convert C code to machine code) Assembling (Compile the necessary libraries) Linking (Merge the compiled code with the compiled libraries) Libraries Libraries are pre-written collections of code that can be reused in other programs. On *UNIX systems, they are usually located in the /lib/ and /usr/include directories. Math.h For example, math.h is very useful to implement complex arithmetic operations. ...