3 Replies - 2336 Views - Last Post: 27 February 2013 - 11:40 AM

#1 jimbob1872  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 16
  • Joined: 08-January 13

algorithm time complexity big oh-notation

Posted 27 February 2013 - 08:43 AM

Consider the following algorithm weirdproc on lists:

weirdproc (x) = shalf (x) + weirdproc ( fhalf(x) )

Suppose that shalf, fhalf, and + have time complexities that are linear with re-
spect to the size of the inputs. Write down an expression for the time complexity of
weirdproc for this case and determine its asymptotic solution.

I have this solution from my lecturer :

if x, y are lists of length O(n) then
Tshalf(x), Thalf(x), T((x)(+)(y)) are all O(n)

let T(n)= time taken to execute weirdproc on x, |x| = n

Then T(n) = Tshalf(x) + Thalf(x) + weirdproc(fhalf x) + Tshalf(x) (+) weirdproc(fhalf x)

=O(n) + O(n) + T(n/2) + O(n)

=O(n) + T(n/2)

so T(n) is O(n)



I dont understand how he got this line: O(n) + O(n) + T(n/2) + O(n)

and I dont understand why there are so many Tshalf's and Thalf's in the line above that?

Any help would be great as I have a test covering big O notation tomorrow

Is This A Good Question/Topic? 0
  • +

Replies To: algorithm time complexity big oh-notation

#2 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 337
  • View blog
  • Posts: 730
  • Joined: 27-June 09

Re: algorithm time complexity big oh-notation

Posted 27 February 2013 - 10:38 AM

You need to account for the time taken to accomplish each operation and add all those times together. There are 4 operations, so you will end up with 4 items that contribute to the time

weirdproc (x) = shalf (x) + weirdproc ( fhalf(x) )

Operation 1 = computing shalf(x) -> Tshalf(x) = O(n)
Operation 2 = computing fhalf(x) -> Thalf(x) = O(n)
Operation 3 = computing weirdproc -> T(n/2)
Operation 4 = (+) results of shalf and weirdproc -> Tshalf(+)weirdproc(fhalf x) = O(n)

This post has been edited by mojo666: 27 February 2013 - 10:40 AM

Was This Post Helpful? 1
  • +
  • -

#3 jimbob1872  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 16
  • Joined: 08-January 13

Re: algorithm time complexity big oh-notation

Posted 27 February 2013 - 11:02 AM

Now I see it. The two Thalfs at the end make a full O(n) when they are added am I correct?
Was This Post Helpful? 0
  • +
  • -

#4 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 337
  • View blog
  • Posts: 730
  • Joined: 27-June 09

Re: algorithm time complexity big oh-notation

Posted 27 February 2013 - 11:40 AM

Correct. Those last two elements are just the arguments for the (+) operation and not some function that needs to be computed. I think Tshalf(x) (+) weirdproc(fhalf x) is supposed to be read T(shalf(x) (+) weirdproc(fhalf x)) which might be contributing to the confusion.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1