CODEWITHSUNDEEP
javascriptbig-o
Peter Nguyen
Peter Nguyen

Reputation: 129

Big-O cost of pyramid algorithm

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?

Upvotes: 1

Views: 105

Answers (1)

logi-kal
logi-kal

Reputation: 7880

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).

Upvotes: 2

Related Questions