CODEWITHSUNDEEP
algorithmdata-structuresbig-o
Riadiani
Riadiani

Reputation: 85

Big-O Analysis Homework: Data Structure

I am new to a data structure class and had only touched the subject of Big-O slightly in my previous CS courses. I am still learning about it online, but I just wanted to make sure that I am doing this right. There are some homework questions regarding Big-O analysis and I just wanted to double-check with you guys.

Here are some of the questions that got me confused, and the analysis I made:

//Part (a)
int x = 0;
for(int i = n; i >= 0; i--)             //N times
  if((i % 3) == 0) break;               //Executed O(N) times
    else x += n;                        //Executed O(N) times
Analysis: O(n)

//Part (b)
int x = 0;
for(int i = 0; i < n; i++)              //N times
  for(int j = 0; j < (n * n /3); j++)   //N^2 times
     x += j;                            //Executed O(N^3) times
Analysis: O(N^3)

//Part (c)
int x = 0;
for(int i = 0; i <= n; i++)             //N times
  for(int j = 0; j < (i * i); j++)      //N^2 times
     x += j;                            //Executed O(N^3) times
Analysis: O(N^3)

I am sorry if my analysis is wrong or all over the place, I'm still really new to this concept! Any input and/or explanations would be appreciated. Thank you!

Upvotes: 3

Views: 134

Answers (1)

Adrian
Adrian

Reputation: 15171

Part a: The loop will execute at most three times. Three is a constant upper limit, so the complexity is constant (aka O(1)).

Part b: You are correct about this one.

Part c: Execute this loop in your head and think about how many times x += j run depending on the value of i. If i is zero, then the inner loop will run 0 times, if i is one, the inner loop will run 1 time -- in general, the inner loop will run i^2 (i squared) times. The total number of times that the x += j line will run, when we count the entire thing (outer loop included), will be:

02 + 12 + 22 + 32 + ... + (n - 1)2 + n2

This mathematical expression is equal to (1/6)n(n + 1)(2n + 1) (see here), and O((1/6)n(n + 1)(2n + 1)) is equal to O(n^3). So you got the right answer, but the wrong way.

Upvotes: 3

Related Questions