Is my answer O(n2) runtime or O(n) runtime?


  • 0
    J

    public class Solution {
    public int[] twoSum(int[] nums, int target) {
    for(int x=0; x<nums.length-1; x++){
    for(int y=x+1; y<nums.length; y++){
    if(nums[x]+nums[y]==target){
    int[] data = {x+1,y+1};
    return data;
    }
    }
    }
    return null;
    }
    }


  • 0
    J

    This is worst case O(n^2). You're not technically doing n^2 calculations (really more like n^2 - (n(num[1] + num[last])/2)), but following big-Oh convention, you drop the lower magnitude factors.


  • 0
    C

    Format code properly for others to see your code.
    Anyway, it should be obvious to you it's O(n^2) algorithm when you have two nested for loops (it doesn't matter even if you scan half of the matrix by making y=x+1. O(n^2)/2 is still O(n^2)


  • 0
    J

    thanks, i dont understand yet how could know what runtime is, any book that you recommend for this?


  • 0
    C

    Google is your guide! Try something like Big-O complexity, Algorithm complexity analysis etc.


    http://discrete.gr/complexity/

    http://bigocheatsheet.com/


Log in to reply
 

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