Thread: Running time

  1. #1
    Registered User
    Join Date
    Mar 2005

    Running time

    Hi all,
    My question is as follows:

    Implement a database to maintain the total of all continual assessment marks awarded to students for the next semester. Students start with 0 marks at the beginning of the semester. Ass students complete assignments, the marks they get are added to this total. Let n be the number of students currently enrolled. You should develop a data structure that supports the following 2 operations.

    add(s,m) where 0 <= s < n, m is a Natural number, adds m marks to the total for student s and returns the total.
    query(s), where 0 <= s < n, returns the marks for student s.

    In addition, before the transactions start, the procedure init will be called to perform any initializations that you may require.

    Show how you would implement this database so that add, query, and init all take time O(1) through the use if 3 arrays of size n and a counter. The initial contents of all three arrays are undefined and you may not assume that they have been initialized to any particular value.

    I was thinking the procedure init just initializes the starting marks of the students to be 0. One array, student[n], would be used to store the marks of the n number of students. Another array, flag[n], could be used to reflect the status of each corresponding student[n] cell in the procedure init, i.e. since all arrays are uninitialized, they would contain garbage values. So, say we're dealing with student a, then if flag[a] != 0, set student[a] = flag[a] = 0, before executing the procedures add or query. One problem is that there is still the very slim chance that the garbage value turns out to be 0. Is this possible?

    I think in this way, add, query and init should use only O(1) time, since each time the procedure is called, it only deals with one array element directly. I guess I could use the counter to see if all n number of students have been initialized, and if so, then init need not be executed. However, if I do it this way, what is the extra array for?

    What is a more efficient way to implement the database?

    Thank you.


  2. #2
    Cat Lover
    Join Date
    May 2005
    Sydney, Australia
    One problem is that there is still the very slim chance that the garbage value turns out to be 0. Is this possible?
    It would depend on your compiler, most compilers (for integers) initialise at their lowest value.

    And if the garbage value is what? It saves you needing to set it to 0.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Finding Program Running Time
    By pf732k3 in forum C Programming
    Replies: 6
    Last Post: 03-18-2008, 01:56 PM
  2. Clearing the console
    By beanroaster in forum C++ Programming
    Replies: 53
    Last Post: 09-14-2005, 07:46 PM
  3. running time for memchr()
    By axon in forum C++ Programming
    Replies: 5
    Last Post: 12-04-2003, 11:50 AM
  4. calculating user time and time elapsed
    By Neildadon in forum C++ Programming
    Replies: 0
    Last Post: 02-10-2003, 06:00 PM