# algorithm time complexity big oh-notation

Page 1 of 1

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

### #1 jimbob1872

Reputation: 1
• Posts: 20
• 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

Reputation: 408
• Posts: 882
• 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

### #3 jimbob1872

Reputation: 1
• Posts: 20
• 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?

### #4 mojo666

Reputation: 408
• Posts: 882
• 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.