Awesome q2a theme
Ask us anything
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Blogs
Previous Year
Exams
Recent questions tagged timecomplexity
0
votes
1
answer
Self doubt :Time Complexity Iterative
Can Someone help me understand the timecomplexity of dependent loops? for example, Q1> int i,j; for(i=1;i<n;i=i++) { for(j=1;j<=i;j=j*2) } Q2> int i,j; for(i=1;i<=n/2;i=i++) { for(j=1;j<=i;j++) }
asked
3 days
ago
in
Algorithms
by
donniedarko
(
21
points)

14
views
timecomplexity
selfdoubt
+2
votes
0
answers
GateBook Full Length Test
Which of the following statements is/are true/correct ? A) Professor Ram gives a comparisonbased sorting algorithm that runs in T(n) = 2T(n1)+ 1. There is not enough information to know whether Ram's algorithm is correct. B) Professor ... base 6) so this also should not be the time complexity of a comparison based sorting algorithm. Can anyone confirm?.Thanks in advance
asked
Dec 28, 2020
in
Algorithms
by
Deterministic
(
31
points)

40
views
gatebook
algorithms
timecomplexity
0
votes
1
answer
Applied Ai test series
What is worst case time complexity of Comparison based sorting? O(n) O(nlogn) O(n^2) none of the above
asked
Dec 21, 2020
in
Algorithms
by
GATE2021_ayush
(
5
points)

22
views
timecomplexity
alogorithms
0
votes
1
answer
NIELIT NIC scientistB 2020 setC ques 56
Consider the algorithm that solves problems of size n by recursively solving two subproblems of size n1 and then combining the solutions in constant time.Then the running time of the algorithm would be: O(n) O(logn) O(nlogn) O($n^{2}$)
asked
Nov 26, 2020
in
Algorithms
by
ayush.5
(
99
points)

16
views
timecomplexity
+1
vote
1
answer
NIELIT STA 2018
Given an random unsorted array ‘A’ in which every element is at most ‘d’ distance from is position in sorted array where d<Size(A). If we applied the insertion sort over this array, then the time complexity of algorithm is: O($n\log d$) O($n^2\log d$) O($nd$) O($n^2d$)
asked
Nov 18, 2020
in
Algorithms
by
Sudarshan Bandyopadh
(
11
points)

37
views
algorithms
sorting
timecomplexity
+1
vote
1
answer
Testbook Test series
What is the best case time complexity to find the smallest element in Maxheap implemented using array with n^3 * logn elements? Ω(logn) Ω(n) Ω(n^3logn) Ω(1)
asked
Nov 16, 2020
in
Algorithms
by
rsamarth
(
29
points)

36
views
algorithms
timecomplexity
+1
vote
1
answer
GATE19886 Time Complexity Algorithms
Can someone please explain what this function do with a diagram and what does it mean by payoff and INF and negate INF? https://gateoverflow.in/94363/gate19886i
asked
Nov 6, 2020
in
Algorithms
by
Akshar Ganatra
(
9
points)

16
views
algorithms
timecomplexity
selfdoubt
0
votes
0
answers
Self_doubt, Code sample from Galvin:Implicit Threading (with few modifications)
asked
Aug 31, 2020
in
Algorithms
by
Nikhil_dhama
(
151
points)

13
views
selfdoubt
algorithms
threads
timecomplexity
0
votes
2
answers
Self doubt in the Kruskal Algorithm
Why in Kruskal’s Algorithm we use $\textbf{O(V+E)}$ and not $\mathbf{V*E}$ Since, in order to check cycle we use unionfind algorithm whic in worst case takes $\textbf{O(V)}$? Can someone please explain this?
asked
Aug 25, 2020
in
Algorithms
by
`JEET
(
187
points)

40
views
algorithms
algorithms
kruskal
timecomplexity
timecomplexity
0
votes
1
answer
GeekForGeeks
Consider an array consisting of –ve and +ve numbers. What would be the worst case time complexity of an algorithm to segregate the numbers having same sign altogether i.e all +ve on one side and then all ve on the other ? A) O(N) B) O(N Log N) C) O(N * N) D) O(N Log Log N)
asked
Aug 21, 2020
in
DS
by
Musa
(
5
points)

49
views
arrays
timecomplexity
0
votes
1
answer
Algorithms (Time Complexity)
The outer loop is running O(log(n)) times and the inner loop is running O(n) times. The answer is given O(n). Will it be the same case if the time complexity of the inner loop is more than the outer loop? Please give a solution with complete analysis.
asked
Aug 9, 2020
in
Algorithms
by
Mellophi
(
363
points)

18
views
algorithms
timecomplexity
0
votes
0
answers
Geekforgeeks Contest  Algorithms
Huffman coding is a lossless data compression algorithm. The most frequent character gets the smallest code and the least frequent character gets the largest code. Consider the following statements regarding Huffman coding algorithm? S1 : The time ... statements S1, S2, and S3 are correct. I am not getting proper explanation on Geekforgeeks for this question.
asked
Aug 1, 2020
in
Algorithms
by
anurag_yo
(
5
points)

14
views
algorithms
timecomplexity
huffmancode
binarytree
0
votes
1
answer
Self Doubt:Time Complexity
What is time complexity to find median of medians?
asked
Jun 30, 2020
in
Algorithms
by
srestha
(
1k
points)

51
views
timecomplexity
0
votes
1
answer
Time complexity
#include <stdio.h> int main(void){ // Your code here! for(int i=1;i<=4;i++) { // printf("%d\n",i); for(int j=1; j<=i;j++) { printf("%s\n", "pankaj"); } printf("\n"); } } i think time complexity is n^2 ...is it right?
asked
Jun 19, 2020
in
Programming
by
pppankajsaini
(
9
points)

38
views
timecomplexity
algorithms
0
votes
1
answer
Time Complexity  Self Doubt Question
asked
Jun 13, 2020
in
Algorithms
by
2207akash
(
5
points)

26
views
timecomplexity
algorithms
iterativecomplexity
0
votes
1
answer
SelfDoubt CLRS
How does the partition algorithm has O(1) space complexity instead of O(N) if it modifies the input array itself even if it doesn't use any extra space?
asked
Jun 10, 2020
in
Algorithms
by
nvs16
(
9
points)

16
views
timecomplexity
algorithms
clrsbook
0
votes
2
answers
Time complexity of below program
what should be the time complexity of below program anyone can anyone please explain for(i=1;i<=n:++i) { for(i=1;i<=n^2:++i) { for(i=1;i<=n^3:++i) { x=y+z; } } }
asked
May 23, 2020
in
Programming
by
Sumit goyal 2
(
5
points)

20
views
algorithms
recurrencerelations
timecomplexity
0
votes
0
answers
https://www.youtube.com/watch?time_continue=1&v=mZjkxOknmhU&feature=emb_logo
asked
May 7, 2020
in
Algorithms
by
Deb Prakash
(
5
points)

52
views
algorithum
asymptoticnotations
timecomplexity
0
votes
1
answer
Clrs book,mit Assignment
$T(n) =2^{n}T(n/2) +n^{n}$
asked
May 5, 2020
in
Algorithms
by
Palash yadav
(
9
points)

52
views
timecomplexity
clrsbook
algorithms
+1
vote
1
answer
Find time complexity of T(n) = 2*T(n1) + 3*T(n2)
asked
Apr 23, 2020
in
Algorithms
by
roh
(
9
points)

36
views
algorithms
timecomplexity
recurrencerelations
timecomplexity
0
votes
1
answer
Complexity analysis of algorithms
What is the time complexity of the below algorithm: sum = 0; for(i=0; i<=n; i++){ for(j=1; j<= i; j=j*2){ sum = sum + j } }
asked
Apr 20, 2020
in
Algorithms
by
roh
(
9
points)

35
views
algorithms
timecomplexity
0
votes
1
answer
GATE2016215 Video Solution
$N$ items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decreasekey operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the ... together? $O(\log^{2} N)$ $O(N)$ $O(N^{2})$ $\Theta\left(N^{2}\log N\right)$
asked
Apr 18, 2020
in
DS
by
admin
(
569
points)

19
views
gate20162
datastructures
linkedlists
timecomplexity
normal
videosolution
0
votes
0
answers
GATE200715,ISRO201626 Video Solution
Consider the following segment of Ccode: int j, n; j = 1; while (j <= n) j = j * 2; The number of comparisons made in the execution of the loop for any $n > 0$ is: $\lceil \log_2n \rceil +1$ $n$ $\lceil \log_2n \rceil$ $\lfloor \log_2n \rfloor +1$
asked
Apr 18, 2020
in
Algorithms
by
admin
(
569
points)

8
views
gate2007
algorithms
timecomplexity
normal
isro2016
videosolution
0
votes
0
answers
GATE2014142 Video Solution
Consider the following pseudo code. What is the total number of multiplications to be performed? D = 2 for i = 1 to n do for j = i to n do for k = j + 1 to n do D = D * 3 Half of the product of the $3$ consecutive integers. Onethird of the product of the $3$ consecutive integers. Onesixth of the product of the $3$ consecutive integers. None of the above.
asked
Apr 18, 2020
in
Algorithms
by
admin
(
569
points)

6
views
gate20141
algorithms
timecomplexity
normal
videosolution
0
votes
0
answers
GATE200840 Video Solution
The minimum number of comparisons required to determine if an integer appears more than $\frac{n}{2}$ times in a sorted array of $n$ integers is $\Theta(n)$ $\Theta(\log n)$ $\Theta(\log^*n)$ $\Theta(1)$
asked
Apr 18, 2020
in
Algorithms
by
admin
(
569
points)

11
views
gate2008
normal
algorithms
timecomplexity
videosolution
0
votes
0
answers
GATE200366 Video Solution
The cube root of a natural number $n$ is defined as the largest natural number $m$ such that $(m^3 \leq n)$ . The complexity of computing the cube root of $n$ ($n$ is represented by binary notation) is $O(n)$ but not $O(n^{0.5})$ $O(n^{0.5})$ ... constant $m>0$ $O( (\log \log n)^k )$ for some constant $k > 0.5$, but not $O( (\log \log n)^{0.5} )$
asked
Apr 18, 2020
in
Algorithms
by
admin
(
569
points)

13
views
gate2003
algorithms
timecomplexity
normal
videosolution
0
votes
0
answers
GATE200745 Video Solution
What is the $\text{time complexity}$ of the following recursive function? int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor (sqrt(n))) + n); } $\Theta(n^2)$ $\Theta(n \log_2n)$ $\Theta(\log_2n)$ $\Theta(\log_2\log_2n)$
asked
Apr 18, 2020
in
Algorithms
by
admin
(
569
points)

8
views
gate2007
algorithms
timecomplexity
normal
videosolution
0
votes
0
answers
GATE2015140 Video Solution
An algorithm performs $(\log N)^{\frac{1}{2}}$ find operations , $N$ insert operations, $(\log N)^{\frac{1}{2}}$ delete operations, and $(\log N)^{\frac{1}{2}}$ decreasekey operations on a set of data items ... if the goal is to achieve the best total asymptotic complexity considering all the operations? Unsorted array Min  heap Sorted array Sorted doubly linked list
asked
Apr 18, 2020
in
Algorithms
by
admin
(
569
points)

10
views
gate20151
algorithms
datastructures
normal
timecomplexity
videosolution
0
votes
0
answers
GATE200744 Video Solution
In the following C function, let $n \geq m$. int gcd(n,m) { if (n%m == 0) return m; n = n%m; return gcd(m,n); } How many recursive calls are made by this function? $\Theta(\log_2n)$ $\Omega(n)$ $\Theta(\log_2\log_2n)$ $\Theta(\sqrt{n})$
asked
Apr 18, 2020
in
Algorithms
by
admin
(
569
points)

5
views
gate2007
algorithms
timecomplexity
normal
videosolution
0
votes
0
answers
GATE200482 Video Solution
Let $A[1,\ldots,n]$ be an array storing a bit ($1$ or $0$) at each location, and $f(m)$ is a function whose time complexity is $\Theta(m)$. Consider the following program fragment written in a C like language: counter = 0; for (i=1; i<=n; i++) { if a[i ... The complexity of this program fragment is $\Omega(n^2)$ $\Omega (n\log n) \text{ and } O(n^2)$ $\Theta(n)$ $o(n)$
asked
Apr 18, 2020
in
Algorithms
by
admin
(
569
points)

9
views
gate2004
algorithms
timecomplexity
normal
videosolution
0
votes
0
answers
GATE200654 Video Solution
Given two arrays of numbers $a_{1},...,a_{n}$ and $b_{1},...,b_{n}$ where each number is $0$ or $1$, the fastest algorithm to find the largest span $(i, j)$ such that $ a_{i}+a_{i+1}+\dots+a_{j}=b_{i}+b_{i+1}+\dots+b_{j}$ or ... time in the key comparison mode Takes $\Theta (n)$ time and space Takes $O(\sqrt n)$ time only if the sum of the $2n$ elements is an even number
asked
Apr 18, 2020
in
Algorithms
by
admin
(
569
points)

7
views
gate2006
algorithms
normal
algorithmdesign
timecomplexity
videosolution
0
votes
0
answers
GATE200750 Video Solution
An array of $n$ numbers is given, where $n$ is an even number. The maximum as well as the minimum of these $n$ numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed? At least $2nc$ comparisons, for some ... $c$ are needed. At most $1.5n2$ comparisons are needed. At least $n\log_2 n$ comparisons are needed None of the above
asked
Apr 18, 2020
in
Algorithms
by
admin
(
569
points)

6
views
gate2007
algorithms
timecomplexity
easy
videosolution
0
votes
0
answers
GATE201937 Video Solution
There are $n$ unsorted arrays: $A_1, A_2, \dots, A_n$. Assume that $n$ is odd.Each of $A_1, A_2, \dots, A_n$ contains $n$ distinct elements. There are no common elements between any two arrays. The worstcase time complexity of computing the median of the medians of $A_1, A_2, \dots , A_n$ is $O(n)$ $O(n \: \log \: n)$ $O(n^2)$ $\Omega (n^2 \log n)$
asked
Apr 18, 2020
in
Algorithms
by
admin
(
569
points)

8
views
gate2019
algorithms
timecomplexity
videosolution
0
votes
0
answers
GATE200847 Video Solution
We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. The total time required for this is $\Theta(\log n)$ $\Theta(n)$ $\Theta(n\log n)$ $\Theta(n^2)$
asked
Apr 18, 2020
in
Algorithms
by
admin
(
569
points)

7
views
gate2008
algorithms
timecomplexity
normal
videosolution
0
votes
0
answers
GATE200615 Video Solution
Consider the following Cprogram fragment in which $i$, $j$ and $n$ are integer variables. for( i = n, j = 0; i > 0; i /= 2, j +=i ); Let $val(j)$ denote the value stored in the variable $j$ after termination of the for loop. Which one of the following is true? $val(j)=\Theta(\log n)$ $val(j)=\Theta (\sqrt{n})$ $val(j)=\Theta( n)$ $val(j)=\Theta (n\log n)$
asked
Apr 18, 2020
in
Algorithms
by
admin
(
569
points)

12
views
gate2006
algorithms
normal
timecomplexity
videosolution
0
votes
0
answers
GATE2017238 Video Solution
Consider the following C function int fun(int n) { int i, j; for(i=1; i<=n; i++) { for (j=1; j<n; j+=i) { printf("%d %d", i, j); } } } Time complexity of $fun$ in terms of $\Theta$ notation is $\Theta(n \sqrt{n})$ $\Theta(n^2)$ $\Theta(n \: \log n)$ $\Theta(n^2 \log n)$
asked
Apr 18, 2020
in
Algorithms
by
admin
(
569
points)

5
views
gate20172
algorithms
timecomplexity
videosolution
0
votes
0
answers
GATE200483, ISRO201540 Video Solution
The time complexity of the following C function is (assume $n > 0$) int recursive (int n) { if(n == 1) return (1); else return (recursive (n1) + recursive (n1)); } $O(n)$ $O(n \log n)$ $O(n^2)$ $O(2^n)$
asked
Apr 18, 2020
in
Algorithms
by
admin
(
569
points)

6
views
gate2004
algorithms
recurrence
timecomplexity
normal
isro2015
videosolution
0
votes
0
answers
GATE2015222 Video Solution
An unordered list contains $n$ distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is $\Theta(n \log n)$ $\Theta(n)$ $\Theta(\log n)$ $\Theta(1)$
asked
Apr 18, 2020
in
Algorithms
by
admin
(
569
points)

6
views
gate20152
algorithms
timecomplexity
easy
videosolution
0
votes
0
answers
GATE200874 Video Solution
Consider the following C functions: int f1 (int n) { if(n == 0  n == 1) return n; else return (2 * f1(n1) + 3 * f1(n2)); } int f2(int n) { int i; int X[N], Y[N], Z[N]; X[0] = Y[0] = Z[0] = 0; X[1] = 1; Y[1] = 2; Z[1] = 3; for(i = 2; ... $f2(n)$ are $\Theta(n)$ and $\Theta(n)$ $\Theta(2^n)$ and $\Theta(n)$ $\Theta(n)$ and $\Theta(2^n)$ $\Theta(2^n)$ and $\Theta(2^n)$
asked
Apr 18, 2020
in
Algorithms
by
admin
(
569
points)

16
views
gate2008
algorithms
timecomplexity
normal
videosolution
0
votes
0
answers
GATE2016239 Video Solution
The given diagram shows the flowchart for a recursive function $A(n)$. Assume that all statements, except for the recursive calls, have $O(1)$ time complexity. If the worst case time complexity of this function is $O(n^{\alpha})$, then the least possible value (accurate up to two decimal positions) of $\alpha$ is ________. Flow chart for Recursive Function $A(n)$.
asked
Apr 18, 2020
in
Algorithms
by
admin
(
569
points)

9
views
gate20162
algorithms
timecomplexity
recurrence
normal
numericalanswers
videosolution
Page:
1
2
3
4
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Recent Posts
New GATEOverflow PDFs
Guidelines to users
No Recent Blog Comments
8,957
questions
3,118
answers
14,337
comments
95,787
users