what is the complexity of my C program?

This is a discussion on what is the complexity of my C program? within the Tech Board forums, part of the Community Boards category; Code: #include <stdio.h> main(){ int ele,in,data[12],p,k; printf("enter your value for prime p:"); scanf("%d",&p); for(ele=1;ele<=p-1;ele++){ for(in=1;in<=p-1;in++){ if(ele*in%p==1){ data[ele]=in; } } } ...

  1. #1
    Registered User
    Join Date
    Jul 2008
    Posts
    9

    what is the complexity of my C program?

    Code:
    #include <stdio.h>
    
    main(){
      int ele,in,data[12],p,k;
      printf("enter your value for prime p:");
      scanf("%d",&p);
      for(ele=1;ele<=p-1;ele++){
        for(in=1;in<=p-1;in++){
          if(ele*in%p==1){
    	data[ele]=in;
          }
        }
      }
     print: printf("Enter the element you want to check:\n"); 
      fflush(stdout);
      scanf("%d",&k);
      printf("Its inverse is: %d\n",data[k]); 
      goto print;
    }
    what's the complexity of this program in terms of variable 'p'?
    give a simple function f(p) of p, such as pp, p or 2p, such that the number of
    steps is O(f(p)), meaning of the order of magnitude of f(p). To be exact, a function
    g(p) is O(f(p)) if there are positive constants c and C such that c <= g(p)/f(p) <= C for all sufficiently large p

  2. #2
    * noops's Avatar
    Join Date
    Jun 2008
    Posts
    108
    This is not a C programming question.

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    That program is a little broken. That array will contain lots of uninitialized values and the bounds checking is the user's responsibility, not to mention unneccessary use of goto, where a simple while(1) would be less to type and convey more info about the intention of the loop.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  4. #4
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    we don't do your homework for you!

    QuantumPete
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  5. #5
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,544
    Since you have data[12], a sufficiently large p creates it's own set of problems.
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    You used a goto and you didn't explicitly make main return int
    FAIL!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    Doesn't matter since the end is never reached.

  8. #8
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Code:
    ele<=p-1
    What's wrong with this?
    Code:
    ele < p
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Issue with program that's calling a function and has a loop
    By tigerfansince84 in forum C++ Programming
    Replies: 9
    Last Post: 11-12-2008, 12:38 PM
  2. Need help with a program, theres something in it for you
    By engstudent363 in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 12:41 PM
  3. Replies: 4
    Last Post: 02-21-2008, 09:39 AM
  4. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 10:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21