Snake_Byte[6] Algorithm Complexity

The Lighter Side of Complexity - The Complexity Project
Your software design?

Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius and a lot of courage to move in the opposite direction.

E.F. Schumacher

First, i hope everyone is safe.

Second, i had meant this for reading over Thanksgiving but transparently I was having technical difficulties with \LATEX rendering and it appears that both MATHJAX and native LATEX are not working on my site. For those interested i even injected the MATHJAX code into my .php header. Hence i had to rewrite a bunch of stuff alas with no equations. Although for some reason unbenowst to me my table worked.

Third, Hey its time for a Snake_Byte [] !

In this installment, i will be discussing Algorithm Complexity and will be using a Python method that i previously wrote about in Snake_Byte[5]: Range.

So what is algorithm complexity?  Well, you may remember in your mathematics or computer science classes “Big Oh” notation.  For those that don’t know this involves both space and time complexity not to be confused with Space-Time Continuums.  

Let’s hit the LazyWeb and particularly Wikipedia:

“Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others collectively called Bachmann–Landau notation or asymptotic notation.”

— Wikipedia’s definition of Big O notation

Hmmm.   Let’s try to parse that a little better shall we?

So you want to figure out how slow or hopefully how fast your code is using fancy algebraic terms and terminology.  So you want to measure the algorithmic behavior as a function of two variables with time complexity and space complexity.  Time is both the throughput as well as how fast from t0-tni1 the algorithm operates.  Then we have space complexity which is literally how much memory (either in memory or persistent memory) the algorithms require as a function of the input.  As an added bonus you can throw around the word asymptotic:

From Dictionary.com

/ (ˌæsɪmˈtɒtɪk) / adjective. of or referring to an asymptote. (of a function, series, formula, etc) approaching a given value or condition, as a variable or an expression containing a variable approaches a limit, usually infinity.

Ergo asymptotic analysis means how the algorithm responds “to” or “with” values that approach ∞.

So “Hey what’s the asymptotic response of the algorithm?”

Hence we need a language that will allow us to say that the computing time, as a function of (n), grows ‘on the order of n3,’ or ‘at most as fast as n3,’ or ‘at least as fast as n *log*n,’ etc.

There are five symbols that are used in the language of comparing the rates of growth of functions they are the following five: ‘o’ (read ‘is little oh of’), O (read ‘is big oh of’), ‘θ’ (read ‘is theta of’), ‘∼’ (read ‘is asymptotically equal to’ or, irreverently, as ‘twiddles’), and Ω (read ‘is omega of’). It is interesting to note there are discrepancies amongst the ranks of computer science and mathematics as to the accuracy and validity of each. We will just keep it simple and say Big-Oh.

So given f(x) and g(x) be two functions of x. Where each of the five symbols above are intended to compare the rapidity of growth of f and g. If we say that f(x) = o(g(x)), then informally we are saying that f grows more slowly than g does when x is very large.

Let’s address the time complexity piece i don’t want to get philosophical on What is Time? So for now and this blog i will make the bounds it just like an arrow t(0) – t(n-1)

That said the analysis of the algorithm is for an order of magnitude not the actual running time. There is a python function called time that we can use to do an exact analysis for the running time.  Remember this is to save you time upfront to gain an understanding of the time complexity before and while you are designing said algorithm.

Most arithmetic operations are constant time; multiplication usually takes longer than addition and subtraction, and division takes even longer, but these run times don’t depend on the magnitude of the operands. Very large integers are an exception; in that case, the run time increases with the number of digits.

So for Indexing operations whether reading or writing elements in a sequence or dictionary are also constant time, regardless of the size of the data structure.

A for loop that traverses a sequence or dictionary is usually linear, as long as all of the operations in the body of the loop are constant time.

The built-in function sum is also linear because it does the same thing, but it tends to be faster because it is a more efficient implementation; in the language of algorithmic analysis, it has a smaller leading coefficient.

If you use the same loop to “add” a list of strings, the run time is quadratic because string concatenation is linear.

The string method join is usually faster because it is linear in the total length of the strings.

So let’s look at an example using the previous aforementioned range built-in function:

So this is much like the linear example above: The lowest complexity is O(1). When we have a loop:


k = 0
for i in range(n):
    for j in range(m):
        print(i)
        k=k+1

In this case for nested loops we multiply the time complexity thus O(n*m). it also works the same for a loop with time complexity (n) we call a function a function with time complexity (m). When calculating complexity we omit the constant regardless if its execution 5 or 100 times.

When you are performing an analysis look for worst-case boundary conditions or examples.

Linear O(n):

for i in range(n):
 if t[i] == 0:
   return 0
return 1

Quadratic O(n**2):

res = 0
for i in range (n):
   for in range (m):
      res += 1
return (res)

There are other types if time complexity like exponential time and factorial time. Exponential Time is O(2**n) and Factorial Time is O(n!).

For space complexity memory has a limit especially if you have ever chased down a heap allocation or trash collection bug. Like we said earlier there is no free lunch you either trade space for time or time for space. Data-driven architectures respond to the input size of the data. Thus the dimensionality of the input space needs to be addressed. If you have a constant number of variables: O(1). If you need to declare an array like using numpy for instance with (n) elements then you have linear space complexity O(n). Remember these are independent of the size of the problem.

For a great book on Algorithm Design and Analysis i highly recommend:

The Algorithm Design Manual by Steven S. Skiena (click it takes you to amazon)

It goes in-depth to growth rates and dominance relations etc `as it relates to graph algorithms, search and sorting as well as cryptographic functions.

There is also a trilogy of sorts called Algorithms Unlocked and Illuminated by Roughgarden and Cormen which are great and less mathematically rigorous if that is not your forte.

Well, i hope this gave you a taste. i had meant this to be a much longer and more in-depth blog however i need to fix this latex issue so i can properly address the matters at hand.

Until then,

#iwishyouwater <- Alexey Molchanov new world freedive record. He is a really awesome human.

Muzak To Blog By: Maddalena (Original Motion Picture Soundtrack) by the Maestro Ennio Morricone – Rest in Power Maestro i have spent many hours listening to your works.

What Is It You WANT?

Hey, it’s not your and its not mine

Hey, I’m just here to share your time

Don’t you pay those spinning wheels no mind

~ Tedeschi Trucks Band

First, i trust this finds everyone safe.

Second, as we head into the holiday season i was thoughting about an interview question i always ask people:

“What is it you want?”

i usually get either contorted faces or a blank stare.  No i didn’t ask you to write a Markov chain algorithm to predict the next meme cryptocurrency or describe the differences between NATS or Kafka distributed processing systems or where do you want to be in five years type of questions.

Let me repeat:

“What is it you want?”

i usually have to prompt folks.  

“Ok, like you want a G5 Gulfstream or an island?  How about a puppy?”

“You want to be a writer?  A painter, a musician, or a teacher?”

Invariably when they answer they want to be doing “something else” as the above profession if money were no object, i always respond, “Then why are you interviewing here? Go do what you just said you wanted to do in the first place.”

Unless you think you want a puppy or a plane. However, there is an unending number of ways to be compensated for your passion. You can have your proverbial cake and eat it as well.

This usually gets people pretty animated.  

Then i ask:

‘Which would you rather be?  Famous or Rich?”

Blanks stares.

You see most people truly don’t think about what they deeply truly desire and want in life.

So i am going to be taking the rest of the year in my non-copious free time to thought about and reflect on what i truly want and desire.

The reason i am using thoughting is that most if not all have thought about this very issue with no answers.  

It’s very interesting at least from what i can tell in western civilization we are not taught to think about what we want when most if not all of what drives us is obtaining something.

Then i have a third question:

“Which is worse a lie or greed?”

None of these questions are as difficult as the first.  However the last one i have people who i have hired in the past who have discussed this question with me for decades.

Most people are petrified of success.  What do you do when you get everything you want?

Charlie don’t forget what happeneed to the man who suddenly got everything he always wanted… He lived Happily Ever After!

~ Willy Wonka

You have to reassess what you want – yet again.

Maybe you don’t really know what you want? It appears most folks just want predictability and control. Well if you could have that isn’t that living in the past because you already know what is going to happen? Just a thought as it were. Maybe you don’t like surprises. Then again the wonder of life is the unexpected.

Or maybe they want power. Power over what exactly?

So go give it some thought.  In the meantime here is a great piece by Alan Watts. He even mentions a Klien Bottle which amazingly someone sent me one which i greatly cherish.

As always would love to see some comments on the posts.

Until then,

#iwishyouwater

tctjr

Muzak To Blog By:  Tedeschi Trucks Band 

Remembering 9.11

“We are dust in time and space.”

~ Of The Wand & Moon.

Today is a day that will live in infamy for many as a testament to what extremist beliefs can conjure into reality. To those who lost loved ones on 9.11.2001 – peace be with you. To those who survived 9.11.2001 – again peace be with you.

For me a different year 9.11.2005 is etched in my mind. It is a strange phenomenon to me as i spend much of my life always optimizing or at least making myself believe that i am optimizing. While i did not lose a father or husband i lost a dear friend and comrade – Steven Swenson.

Today 9.11.2020 one of my true friends and comrades was returning from a freediving trip with his lovely wife and i could hear the joy in both of their voices performing an activity that my comrade Sven died doing what he loved doing on this day in 2005 – freediving. Living underwater on #OneBreath.

i realized through them on this day the essence of it all came to fruition – The_Human_Do_Loop in action and it is ok to truly feel for without the depths we know no true joy.

to roma, leif, and gage – tell him i said hello – again.

i think he would have liked this song.

And I held the breath inside my lungs for days
And I saw myself as one of many waves
When I knew I’d become the ocean’s slave
I just stayed

And we carried far with all the waters past
Of the waves

I was not first I was not last
And if we saw a boat afloat we took the mast
So fast

There’s a part of it, that I’ll miss
At the heart of it, your cold kiss
From the start of it, I know this
Always apart of it

And before too long the waves grew out of hand
And they worked to keep the sea at their command
And the only thing they feared it seemed the sand
And dry land

There’s a part of it, that I’ll miss
At the heart of it, your cold kiss
From the start of it, I know this
Always apart of it

From the water there was born a bright blue roar
As it rolled and formed and calmed the ocean’s floor
And it finally rose and broke upon the shore
No more

There’s a part of it, that I’ll miss
At the heart of it, your cold kiss
From the start of it, I know this
Always apart of it (I know this)

There’s a part of it, that I’ll miss
At the heart of it, your cold kiss
From the start of it, I know this
Always apart of it
Always apart of it

i know at least one person who freedove today loves that song.

until then,

#iwishyouwater

tctjr.