𝗕𝗶𝗴-𝗢 𝗡𝗼𝘁𝗮𝘁𝗶𝗼𝗻 𝗖𝗵𝗲𝗮𝘁 𝗦𝗵𝗲𝗲𝘁

Big O notation is a mathematical shorthand used to describe the runtime of algorithms.

It's a fundamental concept in computer science that helps us understand how an algorithm's performance changes as the input size grows.

𝗕𝗶𝗴-𝗢 𝗡𝗼𝘁𝗮𝘁𝗶𝗼𝗻 expresses the upper bound of an algorithm's runtime (in terms of space or time complexity). It tells us how the algorithm's runtime grows as the input size increases in the worst case.

Time complexity measures how long an algorithm takes to run, while space complexity measures how much memory an algorithm requires.

To analyze the Big O notation of an algorithm, we need to identify the dominant term in the runtime function.

The dominant term is the term that grows the fastest as the input size increases. All other terms can be ignored.

Examples of time complexity using Big-O notation:

🔵 𝗢(𝟭): 𝗖𝗼𝗻𝘀𝘁𝗮𝗻𝘁 𝘁𝗶𝗺𝗲. The runtime of the algorithm does not depend on the input size. An example is accessing a specific element of an array.

🔵 𝗢(𝗹𝗼𝗴 𝗻): 𝗟𝗼𝗴𝗮𝗿𝗶𝘁𝗵𝗺𝗶𝗰 𝘁𝗶𝗺𝗲. The runtime of the algorithm grows logarithmically with the input size. An example is using binary search to find an element in a sorted array.

🟡 𝗢(𝗻): 𝗟𝗶𝗻𝗲𝗮𝗿 𝘁𝗶𝗺𝗲. The runtime of the algorithm grows linearly with the input size. An example is finding an element in an unsorted array.

🟡 𝗢(𝗻 𝗹𝗼𝗴 𝗻): 𝗟𝗼𝗴-𝗹𝗶𝗻𝗲𝗮𝗿 𝘁𝗶𝗺𝗲. The runtime of the algorithm grows log-linearly with the input size. Examples include efficient sorting algorithms such as Quicksort and Heapsort.

🟠 𝗢(𝗻^𝟮): 𝗤𝘂𝗮𝗱𝗿𝗮𝘁𝗶𝗰 𝘁𝗶𝗺𝗲. The algorithm's runtime grows quadratically with the input size. Simple sorting algorithms, such as insertion or selection sort, are examples.

🔴 𝗢(𝟮^𝗻): 𝗘𝘅𝗽𝗼𝗻𝗲𝗻𝘁𝗶𝗮𝗹 𝘁𝗶𝗺𝗲. The runtime of the algorithm grows exponentially with the input size. An example is the recursive Fibonacci method.

♻️ Reshare if you found this helpful.