-2

In my course of algorithms we talk about time complexity with Big O Notation. And I am always confused when I try to calculate the Big O. I know for example when a function then it can be O(n) or O(n²). But I don't know the logical background and how to get this solution for each function.

int func1(int n){ 
   for (int i=1; i<n; i=i*2) 
   printf("i = %d", i); return i; 
}

int func2(int a, int b) {
   int result=1; 
   while (b>0) {
      result = result*a; 
      b = b-1; 
   }
   return result;
}

void func3(int n) {
   for (int i=0; i<pow(2,n); i++) 
      printf("%d", i);  
}
John Coleman
  • 51,337
  • 7
  • 54
  • 119
flowers1234
  • 339
  • 2
  • 9
  • 21

1 Answers1

-1

Big O notation is talking about worst case, how long will the function run?

If you have Func2, with b = 1, six instructions run. Assignment, Comparison, Assignment, Assignment, Comparison, Return. When b = 2, 9 instructions are run. We can tell right away that the number of instructions is 3+(3*n). When talking about how long the function will take, we ignore constants both added to our variable, and multiplied by our variable. Because ultimately, when b=1000, that's the overriding factor of how long the function takes to run. And because it increases Linearly with respect to b, the function is said to be O(n) time. (Big O notation always uses 'n' for its variable.)

The first function increases even slower with respect to n, it increases Logarithmically, only adding more computation for each power of 2 that n passes. (More computation when n = 2, 4, 8, 16, 32, etc)

(Assuming pow(2,n) = n squared; sometimes pow(2,n) = 2 to the power of n) The third function runs the loop once when n = 1, and 4 times when n = 2, we can see that we're talking about n^2 number of iterations through the loop. This is Exponentially expanding, so it's O(n^2) time.

The way to analyze things for Big O notation is to identify how many instructions run based on n = 1, 2, 3, 4... n Make that a function and identify whether it's Constant (doesn't change based on n), Linear (changes directly proportional to n), Logarithmic (changes based on log(n)), Exponential (changes based on a power of n) or otherwise. (It's been a while, but I remember an n log n type and one that talked about when n is a power that some other exponent is raised to, but memory is hazy on those.)

Wesley Holland
  • 44
  • 5
  • I do very much agree that you should directly ask your professor this question, though. All I can do is quote a lesson, but they can walk you through it and find out where you're stumbling. – Wesley Holland Jun 22 '17 at 17:31
  • thank you so much for your answer I am going to understand it. You wrote _If you have Func1, with n = 1, six instructions run. Assignment, Comparison, Printf, Assignment, Comparison, Return. When n = 2, 9 instructions are run. We can tell right away that the number of instructions is 3+(3*n)._ That means I have to understand the function **line by line** to determine the Big O ? – flowers1234 Jun 22 '17 at 17:55
  • Essentially, yes. You can shortcut it a little and look at any repetition in the function. Look for loops (for, while) or for function calls (recursion, if it calls itself...) When starting out, it helps to just list out exactly how many lines will execute, though. – Wesley Holland Jun 22 '17 at 18:03
  • 1
    Func1 is not O(n). It's O(log(n)). (Check how i increments) – Scott Mermelstein Jun 22 '17 at 18:05
  • 1
    Also, it's very likely that Func3 *is* 2^n, not n^2, because that's the standard way of understanding the function, and because that's the C way, which is what mrleo said the programming language is meant to be. Also, if you only wanted n^2, you'd probably type n*n. – Scott Mermelstein Jun 22 '17 at 18:09
  • Now I am really confused.... @ScottMermelstein , how do you get the answer O(log(n))??? – flowers1234 Jun 23 '17 at 05:59
  • 1
    When n = 100, how many I will there be? I= 1, 2, 4, 8, 16, 32, 64. When n = 128 same thing. (You get one more I from n=129 to n=256.) The number of times through the loop is always log (base 2) of n. In big O calculations, we don't care if it's log base 10 or log base 2. Either way, it's O(log(n)). – Scott Mermelstein Jun 23 '17 at 07:26
  • Thanks, @ScottMermelstein, I've corrected the answer to give the correct analysis of the first function. I'm leaving the Exponential explanation, though I agree it's probably 2^n, I can't remember the name of that kind of growth. – Wesley Holland Jun 23 '17 at 20:00