WHAT WOULD BE THE TIME COMPLEXITY OF THIS ALGORITHM


  • -1

    My solution was accepted but I'm having a tough time figuring out what the time complexity would be for this solution. The number of operations by list is 1 + 2 + 3 + 4 + .... + n would number of operations reduce to n^2 how does the math work and translate into Big-O notation?

    I'm thinking this is similar to the gauss formula n(n-1)/2 so O(n^2) but I could be wrong any help is much appreciated

    I'm not submitting this as an answer it is a question so i have not gave a detailed explanation of my code. I can If needed though

    public class Solution {
        public List<List<Integer>> generate(int numRows) {
            if(numRows < 1) return new ArrayList<List<Integer>>();;
            List<List<Integer>> pyramidVal = new ArrayList<List<Integer>>();
            
            for(int i = 0; i < numRows; i++){
                List<Integer> tempList = new ArrayList<Integer>();
                tempList.add(1);
                for(int j = 1; j < i; j++){
                    tempList.add(pyramidVal.get(i - 1).get(j) + pyramidVal.get(i - 1).get(j -1));
                }
                if(i > 0) tempList.add(1);
                pyramidVal.add(tempList);
            }
            return pyramidVal;
        }
    }

  • 0
    J

    I'm getting O(n^2) as well but I'm mostly commenting so that I can get notifications if anyone else answers.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.