Big O Notation

As I prepare for technical interviews for coding jobs, one thing keeps coming up: Big O. I’m always like, “Yea… complexity… time… space… I know it.” So… I set out to really learn it.

Big O notation is a BIG topic. I realized pretty quickly that I’m not going to be able to learn ALL there is to know about it, but I want to understand the most important things, so that I can have a basic foundational knowledge to build on when Big O comes up.

Big O notation describes the complexity of an algorithm. So, how long an algorithm takes to execute or the space used up by an algorithm. Basically, how efficient your algorithm is.

Big O indicates how your program will scale when the input increases. The efficiency of your algorithms can dramatically change the speed and user experience of your program, so you need to be able to predict how the runtime will change given different inputs.

is a constant time algorithm. This means it always executes in the same time and space regardless of the size of the input. The runtime stays consistent whether the input is 1 or 1,000. More input, same time.

ex. grabbing an item from an array from a specific index

is a linear time algorithm. As the input size increases, the time it takes to execute increases. More input, more time.

ex. traversing an array

is a quadratic time algorithm. When you take each element and do something with each other element, like with nested loops.

is an algorithm where growth doubles every time input is added to the data set. So, an exponential growth curve.

ex. recursive functions

is a logarithmic time algorithm. Very efficient. Produces a growth curve that peaks at the beginning then flattens out. So, more input doesn’t change your runtime enough to matter.

Related posts:

None of the MBA students know what got us in, but I have a personal belief that my essay was a big part of it. Hoping resilience and focus to everyone that is still in the process of applying for…

I wrote this poem the other day. I can definitely say that I poured my heart into it, so I hope you enjoy it! I really need some change of weather I`m waiting for bright days to come It feels like…

Over the last few weeks on Medium I have noticed a very large disparity between the amount of views my carefully crafted and edited stories get, versus the amount of views and reactions to a…