One Stop GATE Forum: gate 2006 questions

Message

   A cpu has a five stage pipeline and runs at 1
GHz fre. Instruction fetch happens in the first stage of the pipeline.
A conditional btanch instr. computes the target address and evaluates
the condition in the third stage of the pipeline. The processor stops
fetching new instructions following a conditional brach until the
branch outcome is known. A prg executes 10^9

instructions out of which 20% are conditional branches. If each
instruction take one cycle to complete on avg the total execution time
of the prg is

a]  1.o sec

b]  1.2 sec

c]  1.4 sec

d]  1.6 sec

--------------------

 in q.52 it is written:

" The median of n elements can be found in O(n) time"

---------------

see also q.54 "hard one"

how is it possible?

to find median from unsorted array we have to first sort it which takes     O(n^2) time.

Author	Message
Adhiti Newbie Joined: 02Feb2007 Online Status: Offline Posts: 32	Topic: gate 2006 questions Posted: 02Feb2007 at 11:54am
	A cpu has a five stage pipeline and runs at 1 GHz fre. Instruction fetch happens in the first stage of the pipeline. A conditional btanch instr. computes the target address and evaluates the condition in the third stage of the pipeline. The processor stops fetching new instructions following a conditional brach until the branch outcome is known. A prg executes 10^9 instructions out of which 20% are conditional branches. If each instruction take one cycle to complete on avg the total execution time of the prg is a] 1.o sec b] 1.2 sec c] 1.4 sec d] 1.6 sec -------------------- in q.52 it is written: " The median of n elements can be found in O(n) time" --------------- see also q.54 "hard one" how is it possible? to find median from unsorted array we have to first sort it which takes O(n^2) time. Post Resume: Click here to Upload your Resume & Apply for Jobs

	IP Logged

Alok Newbie Joined: 02Feb2007 Online Status: Offline Posts: 19	Posted: 02Feb2007 at 4:31pm
	I think if u have median as pivot element then u will get balanced partitioned, as median is the middle most element. so complexity will be Theta(n log n) which is option B i may be wrong, please correct me !
	IP Logged


One Stop GATE Forum : GATE Previous Years Test Papers - Discuss Here : CS Papers