Big-O cost of pyramid algorithm

user_9450459 0
Viewed 82

I'm working through trying to understand big-O notation, and I was wondering: what would be the big-O cost of a pyramid algorithm?

pyramid(2) results in:

 # 
###

I know one way of solving it is using nested for-loops like:

function pyramid(n) {
    const totalLengthOfRow = n * 2 - 1
    for (let row = 0; row < n; row++) {
        var line = ''
        var middleCol = Math.floor(totalLengthOfRow / 2)
        
        for (let col = 0; col < totalLengthOfRow; col++) {
            if (col >= middleCol - row && col <= middleCol + row) {
                line += '#'
            } else {
                line += ' '
            }
        }
        console.log(line)
    }
}

So that should be O(n2) right? Since both for-loops grow as n grows. But what if I use string.repeat and get rid of the inner for loop?

Something like:

const numberOfHashes = 1 + row * 2
const numberOfSpaces = n * 2 - 1 - numberOfHashes    
var line = ' '.repeat(numberOfSpaces / 2) + '#'.repeat(numberOfHashes) + ' '.repeat(numberOfSpaces / 2)

Is repeat just like a for-loop, since it also repeats based on the size of n?

big-o javascript
1 Answers

Let's say the second algorithm is a bit smarter, because at each step you don't need to check (with the conditional statement) which character you have to print.

Nevertheless, the JS repeat function is no more than syntactic sugar for a loop. Thus, the two algorithms are (not only semantically, but also asymptotically) equivalent and, in particular, both are O(n^2).

user_46077330
Related