How does Big O affect your programming decision?

[xcodes]

For programmers and web developers, how does Big O affect your programming habit/decision in your day-to-day work?

 

[davidktw]

For programmers and web developers, how does Big O affect your programming habit/decision in your day-to-day work?

All the time. No amount of optimisation in the codes will surpass the algorithmic performance you can get by choosing the right algorithm or right data structure that solve the problem in the most efficient manner.

Be noted that when discussing Big-O notation, the considerations of where you are going for best case, average case or worst case matters. I realise there exist discussion on algorithm that only touch on average case or best case scenarios and neglected that worst case scenarios exist. When deciding which algorithm to use, the kind of input or situation that can result in worst cast scenarios should also be taken into account

However there are always caveats - devil in the details. For example, while quicksort may seems like a very optimal algorithm to performing sort, it may not necessarily be faster than a simple bubble sort in some scenario, especially when your input size is really small. That is because bubble sort is a very simple algorithm and implementing it produce small and efficient code as oppose to the more complicated quicksort, which a naive solution will be using recursion. Even if you don’t use recursion, you may still need to resort a stack-based solution. When your input size is small, the complexity of the algorithm implementation carry higher cost than the algorithm complexity gains. Big-O often assessed under the condition that the input is very large, hence an efficient algorithm shines.

Another example is that I will verbally test candidates between a choice of using an array or a linked list, which will they choose to implement a stack? What are the pros and cons of using each? I want to know if the candidate knows the behaviour of a stack, and how to implement it correctly using a linked list despite we know assessing an element in a linked list is O, while array is O(1). Yet if we just need a stack, a link list will work out to be more effective despite the time complexity seems to be going against a linked-list.

When doing real work, you have to consider the size of the input, the constraint of the environment you are running in, the nature of the input, so forth. These considerations must be taken into account on top of time and space complexity. Otherwise it will just be purely academic and not practical.

 

[xcodes]

Bro david, in this day and age, with hardware is more powerful, does it mean that time complexity is more important than space complexity?

 

[davidktw]

Bro david, in this day and age, with hardware is more powerful, does it mean that time complexity is more important than space complexity?

Suppose I let your hardware speed up by 100 times each day, can your hardware go faster than input going to infinity to surpass them? That is the input size time and space complex is measured upon. Academically the argument for complexity doesn’t change with the improvement of hardware.

But obviously when it comes to practicality, the argument doesn’t hold. If your hardware processing computer can increment at the rate of 100 times daily, you might not have enough input to stress it. Earth population is not growing by 100 times daily. The problem we are solving might be difficult by today’s processing power, but with 100 times performance gain daily, a year of waiting would easily make a difficult problem seemingly easier to solve.

In the case of Security, if the processing power increase at 100 times daily, a max of 4096 bits key sizes will simply not provide sufficient keyspace (input size) for the problem to be difficult enough by next year or just years; that means we will either need a larger keyspace, or we need a different algorithm that doesn’t speed up at the same rate.

Next to address your time vs space complexity concern. Space here is not input space, but working space of the algorithm. Some algorithm takes large amount of memory to work, those algorithms normally attempt to trade space complexity for more efficient time complexity, using techniques such as memoization or dynamic programming. Unless your hardware space can grow to infinity, it wouldn’t be academically faster than an input that is sized to infinity.

The same argument also applies as of how I explain to you with regards to time complexity.

 

[xcodes]

Thanks Bro david, nice read from your post ...

 

[jace_tiff]

thxthxthxthxthx