1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Data structure and algorithms time computation?

  1. Feb 16, 2016 #1
    • Moved from a technical forum, so homework template missing.
    Assume the following set of instructions:

    1. i = 0
    2. if i < n, goto line 6
    3. if A [ i ] = = x, goto line 7
    4. i++
    5. goto line 2
    6. return false
    7. return true

    Assume that line i take Ci time, where Ci is a constant. The worst case total time of running this block of code can be calculated as: C1 + (n+1)C2 + nC3 + nC4 + nC5 + C6 = (C2 + C3 + C4 + C5)n + (C1 + C2 + C6) = An + B, where A = C2 + C3 + C4 + C5 and B = C1 + C2 + C6 are both constants.

    is this right ?
     
    Last edited by a moderator: Feb 17, 2016
  2. jcsd
  3. Feb 17, 2016 #2
    If n is 1 what will happen the first time line 2 is executed? Fix this so it works as intended and the rest of the answer is OK.

    Please use a homework forum and template for homework or similar questions.
     
  4. Feb 17, 2016 #3
    sorry it is supposed to be i >= n not i < n, regarding the homework thing : i didn't get this topic from college but from this site https://www.cpp.edu/~ftang/courses/CS240/lectures/analysis.htm while i was reading about algorithms. i saw that somethings in it are not right so i made some changes to it and asked about it after changing. sorry for any inconvenience
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted