Recent questions tagged time-complexity - GATE CSE Doubts

0 votes

1 answer

Made Easy Mock 2
int s=0; for(int b=1;b<=n;b*=2) { for(int i=0;i<b;i++) { for(int j=0;j<n;j+=2) { s=s+j; } for(int j=1;j<n;j*=2) { s=s+j; } } } What is the TC of above code? Please illustrate the sigma summation method.

asked 2 days ago in Algorithms by Sambhrant Maurya (335 points) | 36 views

0 votes

0 answers

Ace Academy test Series : Time Complexity

asked 4 days ago in Algorithms by Chirag Shilwant (150 points) | 15 views

0 votes

0 answers

Madeeasy test series - Increase order of function
I tried this by taking some bigger values of n and then comparing the results but getting the different answer then the one they have given. Please help.

asked Jan 8 in Algorithms by luc_Bloodstone (33 points) | 12 views

0 votes

0 answers

Made easy test series : Time complexity

asked Jan 6 in Programming by Chirag Shilwant (150 points) | 64 views

0 votes

1 answer

Self Doubt:Algorithm Time complexity
$If$ $t1(n) = Ο(f(n)),$ $t2(n)= Ο(g(n)).$ $Then$ $t1(n).t2(n)= O(f(n)*g(n))$ $Is$ $the$ $above$ $statement$ $always$ $TRUE?$

asked Jan 3 in Programming by Debapaul (615 points) | 22 views

0 votes

0 answers

Time Complexity Of Algorithm, GATE 1999
Consider the following algorithms. Assume, procedure $A$ and procedure $B$ take $O (1)$ and $O(1/n)$ unit of time respectively. Derive the time complexity of the algorithm in $O$-notation. algorithm what (n) begin if n = 1 then call A else ... ? We usually don't count the number of function calls that are being made in a recursive function.

asked Jan 2 in Algorithms by goxul (363 points) | 21 views

0 votes

1 answer

Time complexity Ace test series

asked Dec 29, 2019 in Algorithms by Chirag Shilwant (150 points) | 37 views

0 votes

1 answer

ProgrammingLanguageC
#include <stdio.h> int main(void) { void fun(); fun(); fun(); } void fun(){ static int i = 1; auto int j = 5 ; printf("%d",i++); printf("%d",j++); } What will be the output of the code

asked Dec 25, 2019 in Programming by grv_99 (9 points) | 35 views

0 votes

0 answers

Applied course test series : Time complexity of Recurrence relation

asked Dec 18, 2019 in Algorithms by vishal burnwal (117 points) | 35 views

0 votes

0 answers

Made easy test series Algorithms asymptotic

asked Dec 17, 2019 in Algorithms by Chirag Shilwant (150 points) | 14 views

0 votes

1 answer

MULTIPLE SUBJECT : ALGORITHMS + PROGRAMMING AND DATA STRUCTURES (GATE - 2020) - QUESTION 27

asked Dec 12, 2019 in Algorithms by Pratyush Priyam Kuan (736 points) | 16 views

0 votes

0 answers

Made Easy Test: Algorithms
What is the TC of the following? int i,j,k,m=0; for(i=1;i<n;i++){ for(j=1;j<i*i;j++){ if (j%i==0) for(k=1;k<j;k++) m=m+1; } }

asked Dec 10, 2019 in Algorithms by Sambhrant Maurya (335 points) | 13 views

0 votes

1 answer

self doubt on time complexity
What is the recurrence equation and how to solve it?

asked Dec 6, 2019 in Algorithms by Abhipsa Mishra (15 points) | 12 views

0 votes

0 answers

self doubt in algorithms time complexity
What is the answer for this?

asked Dec 6, 2019 in Algorithms by Abhipsa Mishra (15 points) | 3 views

0 votes

1 answer

Solve the recurrence relation: T(n) = T(n^(1/2)) + n

asked Dec 4, 2019 in Algorithms by avistein (355 points) | 9 views

0 votes

0 answers

Self doubt on time complexity calculation
Please show how to calculate time complexity of $T(n) = 3T(n/4) + n^2$ using recursion tree method. Thanks!

asked Nov 29, 2019 in Algorithms by Abhipsa Mishra (15 points) | 15 views

0 votes

0 answers

Self doubt on time complexity calculation
What is the time complexity of the following recurrence equation : T(n) = T(n/2) + T(n/4) + T(n/8) + n I solved it using recursion tree method and I'm getting O(n) as the answer. Please let me know the answer and the procedure you used. Thank you.

asked Nov 29, 2019 in Algorithms by Abhipsa Mishra (15 points) | 16 views

0 votes

1 answer

Madeeasy Test series - time complexity
What is the time complexity of foo() and bar() ? I solved it and get ans correct for foo(), but for bar() I am getting wrong ans, for bar(): T(n) = 2T(n-1) + c; c is constant I solved it and get this: T(n) = 2^(n-1) * 3^n ... bar() is T(n) = O(2^n), I don't understand how they get this. Is my recurrence equation is wrong or something else, please solve this.

asked Nov 29, 2019 in Algorithms by luc_Bloodstone (33 points) | 25 views

0 votes

1 answer

MadeEasy Test Series - Calculate time complexity
What is the time complexity of below function? Can we able to solve it by Masters Theorem?

asked Nov 25, 2019 in Algorithms by luc_Bloodstone (33 points) | 28 views

0 votes

0 answers

Ace Test Offline
i=n; while(i>0) { k=1; for(j=0;j<=n;j+=k) k++; i/=2; } The time complexity of following piece of code is: $O(nlog(n))$ $O(log^2n)$ $O(n^2)$ $O(log(n*sqrt(n)) $

asked Nov 17, 2019 in Algorithms by Akash Papnai (13 points) | 25 views

0 votes

0 answers

Applied Gate Test series
Find the time complexity of codes below – for(i=1;i<n*n*n*;i*=n) { for(j=0;j<n;j+=2) { for(k=1;k<n;k*=3) { //constant; } } } for(i=0;i<n;i++) { if(i mod 2 ==0) { for(j=i;j<n;j++) { if(i%2==0 && j%2==0) printf("Gate 2020"); } } }

asked Nov 3, 2019 in Algorithms by MRINMOY_HALDER (37 points) | 36 views

0 votes

0 answers

TIme complexity Made easy
What is time complexity for this function?

asked Oct 17, 2019 in Algorithms by vupadhayayx86 (6 points) | 26 views

0 votes

0 answers

geekforgeeks
int a = 0; for (i = 0; i < N; i++) { for (j = N; j > i; j--) { a = a + i + j; } } my doubt is an inner loop (J) is depend on i variable which is run n times. now how to evaluate the inner loop. please explain in details how TC is calculated.

asked Oct 10, 2019 in Algorithms by Hira Thakur (8 points) | 10 views

0 votes

1 answer

MadeEasy Workbook, DRDO 2008
Consider a sequence A of length n which is sorted except for one item that appears out of order.Which of the following can sort the sequence in O(n) time? (a) Heap sort (b) Quick sort (c) Merge sort (d) Insertion sort

asked Oct 9, 2019 in Algorithms by Ansaaa24 (9 points) | 32 views

0 votes

2 answers

made easy test series quick sort time complexity

asked Sep 20, 2019 in Algorithms by ck (10 points) | 24 views

0 votes

0 answers

Made easy Test Series question....
Consider th following cases for quick sort to sort an array of n element $a[0...n-1]$ i) Choosing the pivot element randomly from the given array ii) choosing median element as pivot. Iii) Choosing middle element as pivot For which of the above cases quick sort always gives $O(nlogn)$ time complexity?

asked Sep 11, 2019 in Algorithms by `JEET (178 points) | 14 views

0 votes

2 answers

Made easy test series question.
For the below message number of bits required in Huffman Coding is: abbaabccdabcd

asked Sep 11, 2019 in Algorithms by `JEET (178 points) | 28 views

0 votes

1 answer

Made easy test series.
Let $g(n) = \Omega(n)$, $f(n) = O(n)$ and $h(n) = \theta(n)$ then what is the time complexity of $[g(n) f(n) + h(n)]$ How to solve such questions?

asked Sep 11, 2019 in Algorithms by `JEET (178 points) | 18 views

0 votes

0 answers

Made Easy online test series
Consider an array A of length n, array contain number between (1 – 10), in any arbitary order, best sorting algorithm takes $650$ ns if $n = 50$, the time required by algorithm if n = 300.

asked Sep 11, 2019 in Algorithms by `JEET (178 points) | 12 views

+1 vote

2 answers

what does tightest lower bound means??
Here the tightest lower bound means?. (Please suggest some source if possible for such questions) https://gateoverflow.in/1026/gate2004-29

asked Aug 26, 2019 in Algorithms by Rishav_Bhatt (13 points) | 34 views

0 votes

3 answers

Algorithms - Time Complexity analysis
1 .Let P be the problem. Suppose that the worst case asymptotic running time complexity of P is in O($n^2$lgn) and is also in Ω(n). Now let A be an algorithm that solves P. Which of the following is correct about A: A has worst-case time ... time case complexity of an algorithm is θ(n). The Algorithm executes in time T(n) = Ω($n^2$) for every input data.

asked Aug 22, 2019 in Algorithms by sagar2405 (149 points) | 57 views

0 votes

0 answers

Algorithms - Time complexity
1 .Solve the recurrence: $T(n) = 2T(\sqrt n) + log\ n$ $T(n) = T(\frac{n}{2}) + 2T(\frac{n}{4}) +n$ 2 .$f(n) = n^{1.01}$ and $g(n) = n(log\ n)^2$ then which one is true $f(n) = O(g(n))$ $f(n) = \Omega(g(n))$ $f(n) = \Theta(g(n))$ 3 . $f(n) = n^{\frac{1}{2}}, g(n) = 1$, then is it correct $g(n) = o(fn)$ {$o$ = small o Not big $O$} Please solve the above questions.

asked Aug 22, 2019 in Algorithms by sagar2405 (149 points) | 18 views

0 votes

0 answers

Algorithms: Asymptotic Analysis
The decreasing asymptotic order of the functions: F1:$2^{2^{n+1}}$ F2: log*log n F3: log log* n F4: (log n)! F5: $n^{log log n}$ F1,F5,F4,F2,F3 F1,F4,F5,F3,F2 F1,F5,F4,F2,F3 None of these

asked Aug 5, 2019 in Algorithms by Sambhrant Maurya (335 points) | 17 views

+1 vote

1 answer

Asymptotic Analysis
Consider the following functions: $f(n)=\Omega(n^{3}) $ $g(n)=O(n^{2})$ $h(n)=\Theta (n^{2})$ Which one of the following is the correct asymptotic representation of f(n) + g(n) * h(n) ? $\Omega (n^{3})$ O($n^{4}$) $\Theta (n^{3})$ $\Omega (n^{4})$

asked Aug 4, 2019 in Algorithms by Sambhrant Maurya (335 points) | 35 views

+1 vote

0 answers

How to solve this recurrence relation?
T(n)=T(k)+T(n−k−1)+θ(n) Can someone explain how to solve this?

asked Jul 30, 2019 in Algorithms by iarnav (76 points) | 15 views

0 votes

0 answers

cs501 Advance Computer Architecture TOPIC NAME: •Hard Disk Transfer Time Calculation

asked Jul 25, 2019 in CO & Architecture by Unaiza fatima (6 points) | 7 views

0 votes

1 answer

Self Doubt; Algorithms
A programmer wants to create a dynamic array implementation of stack in which always a new array of size n+10 is created every time the array cannot accommodate more elements. For example, for inserting the first element, array of size 0+10=10 will be created. After ... this new array. What is the time complexity of this stack implementation? O(n) O(log n) O(nlog n) O(1)

asked Jul 20, 2019 in Algorithms by Sambhrant Maurya (335 points) | 20 views

+1 vote

1 answer

Self Doubt: Algorithms
If n is a multiple of 3, then the minimum number of multiplications needed to calculate $a^{n}$ is?

asked Jul 19, 2019 in Algorithms by Sambhrant Maurya (335 points) | 19 views

+1 vote

2 answers

Time Complexity analysis
What is the time complexity of the following code: for(i=1 to n) { for(j=1 to n) { for(k=j+1 to n) printf(“Something”); } }

asked Jul 17, 2019 in Algorithms by Sambhrant Maurya (335 points) | 32 views

0 votes

2 answers

MadeEasy WorkBook Recurrence Relation
Consider the following function f void f(int n) { if(n <= 0 ) return; else { print(n); f(n-2); print(n); f(n-1); } } Let R(n) be recurrence relation which computes sum of values printed by f(n). Then R(n) is? R(n-1) + R(n-2) R(n-1) + R(n ... For F(n) it's time complexity should by T(n) = T(n-1) + T(n-2) + c I am not able to think what is happening with R(n).

asked Jul 17, 2019 in Algorithms by AliH (10 points) | 23 views

Page:

3,008 questions

1,516 answers

8,984 comments

89,815 users