Thread: Time complexity problem

  1. #1
    Registered User
    Join Date
    Jul 2022
    Posts
    1

    Question Time complexity problem

    Hey, the time complexity here is n^2 . Can someone explain why and how to calculate it? Thanks in advance.
    Code:
    void f(int n)
    {
       for (int i=1; i<=n; i++)
          for (int j=1; j<=n*n/i; j+=i)
              printf(*);
    }

  2. #2
    Registered User rstanley's Avatar
    Join Date
    Jun 2014
    Location
    New York, NY
    Posts
    957
    Quote Originally Posted by Ofir112 View Post
    Hey, the time complexity here is n^2 . Can someone explain why and how to calculate it? Thanks in advance.
    Code:
    void f(int n)
    {
       for (int i=1; i<=n; i++)
          for (int j=1; j<=n*n/i; j+=i)
              printf(“*”);
    }
    I don't see that this has anything to do with "time". Not sure what you are attempting to do here.

    In the future, please provide a complete program that can be compiled and tested. Compare my version below to better explain what the code is doing:

    Code:
    #include <stdio.h>
    
    void f(int n)
    {
      for (int i=1; i<=n; i++)
      {
        for (int j=1; j<=n*n/i; j+=i)
        {
          printf("*"); // putchar('*'); would be better
        }
        putchar('\n');
      }
    
    }
    
    int main(void)
    {
      f(5);
    
      return 0;
    }
    Output:
    Code:
    *************************
    ******
    ***
    **
    *
    Last edited by rstanley; 07-04-2022 at 08:25 AM.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,156
    Rather than printing characters, make a table.
    Code:
    #include <stdio.h>
     
    int f(int n)
    {
      int r = 0;
      for (int i=1; i<=n; i++)
      {
        for (int j=1; j<=n*n/i; j+=i)
        {
          r++;
        }
      }
      return r; 
    }
     
    int main(void)
    {
      for ( int n = 1 ; n < 20 ; n++ ) {
        int O_n2 = n * n;
        printf("f(%2d) = %3d ; O(N^2)=%4d 2*O(N^2)=%4d, 3/2*O(N^2)=%4d\n", 
            n, f(n), O_n2, 2*O_n2, 3*O_n2/2);
      }
      return 0;
    }
    
    $ gcc bar.c
    $ ./a.out 
    f( 1) =   1 ; O(N^2)=   1 2*O(N^2)=   2, 3/2*O(N^2)=   1
    f( 2) =   5 ; O(N^2)=   4 2*O(N^2)=   8, 3/2*O(N^2)=   6
    f( 3) =  12 ; O(N^2)=   9 2*O(N^2)=  18, 3/2*O(N^2)=  13
    f( 4) =  23 ; O(N^2)=  16 2*O(N^2)=  32, 3/2*O(N^2)=  24
    f( 5) =  37 ; O(N^2)=  25 2*O(N^2)=  50, 3/2*O(N^2)=  37
    f( 6) =  55 ; O(N^2)=  36 2*O(N^2)=  72, 3/2*O(N^2)=  54
    f( 7) =  75 ; O(N^2)=  49 2*O(N^2)=  98, 3/2*O(N^2)=  73
    f( 8) =  99 ; O(N^2)=  64 2*O(N^2)= 128, 3/2*O(N^2)=  96
    f( 9) = 127 ; O(N^2)=  81 2*O(N^2)= 162, 3/2*O(N^2)= 121
    f(10) = 157 ; O(N^2)= 100 2*O(N^2)= 200, 3/2*O(N^2)= 150
    f(11) = 192 ; O(N^2)= 121 2*O(N^2)= 242, 3/2*O(N^2)= 181
    f(12) = 228 ; O(N^2)= 144 2*O(N^2)= 288, 3/2*O(N^2)= 216
    f(13) = 269 ; O(N^2)= 169 2*O(N^2)= 338, 3/2*O(N^2)= 253
    f(14) = 313 ; O(N^2)= 196 2*O(N^2)= 392, 3/2*O(N^2)= 294
    f(15) = 360 ; O(N^2)= 225 2*O(N^2)= 450, 3/2*O(N^2)= 337
    f(16) = 412 ; O(N^2)= 256 2*O(N^2)= 512, 3/2*O(N^2)= 384
    f(17) = 463 ; O(N^2)= 289 2*O(N^2)= 578, 3/2*O(N^2)= 433
    f(18) = 521 ; O(N^2)= 324 2*O(N^2)= 648, 3/2*O(N^2)= 486
    f(19) = 582 ; O(N^2)= 361 2*O(N^2)= 722, 3/2*O(N^2)= 541
    You know it's basically going to be O(N^2) because you have two nested loops both involving n.
    The actual scale factor (1,2,3/2) doesn't matter, nor do other minor O(N) terms.

    For sufficiently large N, the fact is that N^2 will completely dominate any other terms.
    Big O notation - Wikipedia
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Approximations on time complexity
    By RyanC in forum General Discussions
    Replies: 1
    Last Post: 12-28-2018, 06:18 AM
  2. Time Complexity
    By ARYAA in forum C Programming
    Replies: 5
    Last Post: 07-06-2016, 03:22 AM
  3. Time complexity.
    By RyanC in forum C Programming
    Replies: 1
    Last Post: 07-10-2015, 01:18 PM
  4. Time complexity of algorithm
    By viblic in forum C Programming
    Replies: 2
    Last Post: 01-11-2012, 11:22 AM
  5. Time Complexity
    By Stuart Dickson in forum C Programming
    Replies: 7
    Last Post: 07-20-2010, 03:13 AM

Tags for this Thread