How to logarithmically write pseudocode?

“Computer Science 101: Master the Theory Behind Programming” is a course on Skill Share that mentioned how logarithms were the fastest way to complete operations.

I want my code to be fast, so how would I write it in a logarithm?

Apparently, a nested for loop (eg.) is one of the slower ways to get a computer to do operations - because n^2, where n is the number of operations, if both loops are the same length.

1 Like

You’re misreading that.
Different tasks take different amounts of work.
Your text does not say that all tasks can be done in the same amount work.

1 Like

I didn’t say that all tasks would be the same amount of work… ?

1 Like

You’re saying all operations

(also, 0 is less than log n, which is the amount of work for something you don’t do at all, that is fastest)

There do exist tasks which can at best be carried out in log n amount of time. But these are not all tasks, some can be done faster, some can’t be done in that amount of time.

1 Like

Keep in mind this isn’t some special programming construct (you’re asking how to write it in pseudo code)

It’s just the amount of work/number of steps that are required to complete a task.

For example, how much work is it to greet everyone in a room?
You could greet everyone one at a time, or you get them all to shush and greet them all at once - these are different amounts of work for the same task.

1 Like

Fair enough. Could you give examples where logarithms can apply?

1 Like

Interesting how the two words are anagrams of each other. (algorithm and logarithm)

3 Likes

How many times does 128 need to be halved to reach 1?

log2 128 = 7
27 = 128

It’s the inverse of exponentiation, same as how division is the inverse to multiplication and subtraction to addition

1 Like

And the only reason it’s related to computer science is that we do stuff with computers and when we want to describe and/or reason about stuff we use math.

So it’s the same as addition/subtraction/multiplication … and so on, there’s nothing special going on

What your text is probably doing is talking about some specific task for which the amount of work required can be described with an expression using logarithms

So again with the room of people to greet.
If there are N people in the room, then it takes

N

Amount of work to greet them one at a time.
If instead greeting them all at once then it takes

1

Amount of work.

To walk around a square with a side of size N, you need to walk 4N amount of distance. To fill a square you need to fill N*N amount of space


If you do operations with trees then you’re likely wondering what the distance from the root to a leaf is. If that tree is balanced, then that depth is log N
If you divide an array repeatedly into two parts as part of sorting (quicksort/mergesort), then log N is going to be the depth of that recursion. At each depth level there will be a total amount of N work, so log N depths N times means that these sorting algorithms complete in N * log N amount of work

4 Likes