CODEWITHSUNDEEP
javaperformanceruntimebig-otheory
user10763705
user10763705

Reputation:

What Big O notation do i have here?

So im having a hard time understanding Big O Notations and are looking for some Examples to understand it better. Now lets look at the following code: 

`public static void main(String[] args)` {

            int N = 4; 
           int sum = 0;

            for (int i = 1; i < N; i = i*2)
            {
                for (int j = 1; j < N; j++)
                {
                    sum++;
                }
            }

Am i assuming correctly that the Big O Notation here would be: O(N log(N))? Because the first for loop runs log(n) times and the second one does N times? If not: What would be the correct Big O Notation here? 


And another example: 

`public static int f(int N){

            if (N<=1)
            {
                return 0;
            }
            return (2*f(N/2));
        }`

What would the Big O notation be here? Is it O(log N)?

As you can see im guessing a little bit, so if you would have any advice on how to identify the correct Big O Notation i would be really grateful!

Upvotes: 0

Views: 61

Answers (1)

Maya Farber Brodsky
Maya Farber Brodsky

Reputation: 316

You are correct about the first case, and your reasoning is correct.

Indeed, the complexity is O(logn) in the second case. Here is one way to think about it:

In every step of the recursion, you divide the number by two, until your reach the base case of one. Thus, the number of times this function is called is the number of times you can divide the number by two until you reach one, which is by definition exactly log(n). Each time you call the function you perform O(1) operations, and thus the total complexity is O(logn).

Upvotes: 1

Related Questions