gate 2006 questions
Printed From: One Stop GATE
Category: GATE Previous Years Test Papers - Discuss Here
Forum Name: CS Papers
Forum Discription: Computer Science Previous Year GATE Papers to can discussed here.
URL: http://forum.onestopgate.com/forum_posts.asp?TID=126
Printed Date: 06Feb2025 at 8:26pm
Topic: gate 2006 questions
Posted By: Adhiti
Subject: gate 2006 questions
Date 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.
|
Replies:
Posted By: Alok
Date 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 !
|
|