Hindi
English

Question

Download Solution PDF

पुनरावृत्ति समीकरण T(n) = T() + O(1) में निम्नलिखित में से कौन-सा अनन्तस्पर्शी हल है?

This question was previously asked in
UPPCL AE CS 2018 Official Paper (Held on 31 Dec 2018)
Download PDF Attempt in App
View all UPPCL Assistant Engineer Papers >
  1. T(n) = O()
  2. T(n) = O()
  3. T(n) = O(log log n)
  4. T(n) = O(log n)

Answer (Detailed Solution Below)

Option 3 : T(n) = O(log log n)
Free Tests
View all Free tests >
Free
ST 1: UPPCL AE - Electric Circuits
20 Qs. 20 Marks 20 Mins
Start Now

Detailed Solution

Download Solution PDF

सही उत्तर विकल्प 3 है।

संकल्पना:

 T(n) = T() + O(1) 

दोनों पक्षों पर log2 लागू करने पर

अतः सही उत्तर T(n) = O(log log n) है।

Download Solution PDF
Latest UPPCL Assistant Engineer Updates

Last updated on Oct 21, 2023

-> The UPPCL AE Notification 2025 will be released soon.

-> The applications must be submitted online.

-> The applicants must have completed B.E./B.Tech.

-> For the 2025 cycle, the recruitment will be through GATE 2025.

-> The salary will be as per Pay Matrix Level 10.

-> Prepare for the exam using UPPCL AE Previous year Papers.

Exams Tests Super Practice

More Introduction Questions

Q1.Assume that P and NP are different i.e. P! = NP then for the expression NP-Complete ∩ P = ? Which among the following is correct ? 
Q2.In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Here, n and m are number of vertices and edges, respectively. Match each algorithm with its time complexity. List I List II Standard graph algorithms Time complexities A. Bellman‐Ford algorithm I. O(m*log n) B. Kruskal’s algorithm II. O(n3) C. Floyd‐Warshall algorithm III.  O(n*m) D. Topological sorting IV. O(n + m) Choose the correct answer from the options given below :
Q3.Two balanced binary trees are given with m and n elements, respectively. They can be merged into a balanced binary search tree in ______ time.
Q4.निम्नलिखित में से कौन-सा केस समय जटिलता की गणना करते समय मौजूद नहीं होता है?
Q5.निम्नलिखित में से किस निर्णय प्रक्रिया में कम से कम द्वि घातीय समय जटिलता होती है?
Q6.एक अनियंत्रित सूची में n विशिष्ट तत्व होते हैं। सूची में दूसरी न्यूनतम से बड़ी सूची में तत्वों को खोजने के लिए तुलनाओं की संख्या ______ है।
Q7.पुनरावृत्ति समीकरण T(n) = T(\(\sqrt{n}\)) + O(1) में निम्नलिखित में से कौन-सा अनन्तस्पर्शी हल है?
Q8.दिए गए विकल्पों में से कौन सा फ़ंक्शन f1, f2, f3 और f4 की स्पर्शोन्मुख जटिलता का बढ़ता क्रम प्रदान करता है? f1 = 2n, f2 = nlgn, f3 = \(n^\sqrt{n}\), f4 = n2
Q9.निम्नलिखित कोड स्निपेट पर विचार करें। यह इनपुट के रूप में एक धनात्मक पूर्णांक n स्वीकार करता है। int i = 0. j = 0, val = 1; for (i = 1; i <= n; i++) {      j = n;      if (i% 2 == 0)    {        while (j > 1)      {         val = val * j;          j = j /2;      }    } } एल्गोरिदम की सबसे खराब स्थिति समय जटिलता क्या है?

More Asymptotic Worst Case Time and Time Complexity Questions

Q1.Assume that P and NP are different i.e. P! = NP then for the expression NP-Complete ∩ P = ? Which among the following is correct ? 
Q2.Given below are two statements: Statement I: If f and g are two functions and f = O(g) but g ≠ o(f), we say that the growth rate of g is smaller than that of f Statement II: The class of all decision problems decided by a TM in exponential time, that is O(2k), k being a constant. In the light of the above statements, choose the most appropriate answer from the options given below.
Q3.Given below are two statements: Let f(n) and g(n) be asymptotically positive functions. The following conjectures are given Statement I: f(n) ≥ 1 and f(n) = O(g(n)) ⇒ g(n) = Ω(f(n)) Statement II: f(n)  = O(g(n)) ⇒ Ig(f(n)) = O(1g(g(n))) where Ig(g(n)) ≥1 for all sufficient large n. In the light of the above statements, choose the most appropriate answer from the options given below. 
Q4.Match List I with List II LIST I LIST II A. The running time of straight forward recursive method to compute nth Fibonacci number Fn I. O (n2) B. The running time to compute Fn using memoization II. O (lg n) C. The running time to compute Fibonacci number Fn using only integer addition and multiplication III. O (n) D. The running time to determine an optimal bitonic tour IV. Θ{ϕn} Choose the correct answer from the options given below:
Q5.Match List I with List II LIST I LIST II A. Parallel FFT I. Θ (n2) B. Iterative FFT II. Θ (n) C. Evaluation of polynomial at n points by Horner method III. Θ (lg n) D. Product of two polynomials that are represented in point value form IV. Θ (n lg n) Choose the correct answer from the options given below:
Q6.Given the FFT we can have ___________ time procedure for multiplying two polynomials A(x) and B(x) of degree bound n where input and output representations are in coefficient form, assuming n is a power of 2.
Q7.Assume that f(n) and g(n) are asymptotically positive. Which of the following is correct?
Q8.The solution of the recurrence relation 7(n) = 3T(n/4) + n lg n is
Q9.In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Here, n and m are number of vertices and edges, respectively. Match each algorithm with its time complexity. List I List II Standard graph algorithms Time complexities A. Bellman‐Ford algorithm I. O(m*log n) B. Kruskal’s algorithm II. O(n3) C. Floyd‐Warshall algorithm III.  O(n*m) D. Topological sorting IV. O(n + m) Choose the correct answer from the options given below :
Suggested Test Series
View All >
AE & JE Electrical Engg. Exams Previous Year Papers Mock Test
276 Total Tests with 9 Free Tests
Start Free Test
Uttar Pradesh (UP) General Knowledge Complete Pack
181 Total Tests with   0 Free Tests
Start Free Test

More Algorithms Questions

Q1.The Highest Lower Bound on the number of Comparisons in the worst case for comparison-based sorting order of : 
Q2.In what manner is a state-space tree for a backtracking algorithm constructed ? 
Q3.Which open addressing technique is free from Clustering problems ?
Q4.Assume that P and NP are different i.e. P! = NP then for the expression NP-Complete ∩ P = ? Which among the following is correct ? 
Q5.The recurrence relation for binary search algorithm is : 
Q6.The time complexity of solving the Longest Common Subsequence problem using Dynamic Programming is : (m and n are lengths of subsequences) 
Q7.Given the following characteristics : (i) Optimal substructure (ii) Overlapping subproblems (iii) Memorization (iv) Decrease and conquer Dynamic programming has the following characteristics :
Q8.Which of the following is not a stable sorting algorithm ?
Q9.Match the LIST-I with LIST-II LIST - I LIST - II A. Breadth First Search I. LISP B. Depth First Search II. Syntax tree C. Prefix III. Stack D. Infix IV. Queue Choose the correct answer from the options given below:
Q10.Which one of the following is not related to the feed forward networks on the Backpropagation Algorithm
Testbook Edu Solutions Pvt. Ltd.
1st & 2nd Floor, Zion Building,
Plot No. 273, Sector 10, Kharghar,
Navi Mumbai - 410210
support@testbook.com
Toll Free:1800 833 0800
Office Hours: 10 AM to 7 PM (all 7 days)
Company
About usCareers We are hiringTeach Online on TestbookPartnersMediaSitemap
Products
Test SeriesTestbook PassOnline CoursesOnline VideosPracticeBlogRefer & EarnBooks
Copyright © 2014-2022 Testbook Edu Solutions Pvt. Ltd.: All rights reserved
User PolicyTermsPrivacy
Hot Links： teen patti gold old version teen patti glory teen patti chart