Questions tagged [big-o-notation]

Big O Notation is an informal name of the "O(x)" notation used to describe asymptotic behaviour of functions. It is a special case of Landau notation.

Filter by
Sorted by
Tagged with
-1
votes
0answers
35 views

Recurrence relation $T(n/10) + T(c·n) + n$

Given the following question: $T(n)=T(n/10)+T(an)+n$ while $a$ is a const and $T(n)=1:(n<10)$ Using a set of complicated equations I found and proved that $a=9/10$ is the correct answer (for sure) ...
0
votes
1answer
27 views

Does $c^n = O(2^n)$ and $log_c(n) = O(log_2(n))$ for any constant $c$?

I thought they did, but recently I tried to express $3^n$ as $k \times 2^n + o(2^n)$ for some constant $k$ but wasn't able to. All I found was $3^n = (\frac{3}{2})^n 2^n$. What am I misunderstanding ...
0
votes
0answers
39 views

Prove that $T(n)=\omega(n)$?

Edit: can someone provide clear answer with all details Given: $T(n)=T(n/10)+T(an)+n$ while $a$ is a const and $T(n)=1:(n<10)$ I was asked to find the minimum value for $a$ for which $T(n)=\omega(n)...
0
votes
1answer
36 views

How can I find this code block's execution time t(n) and big O notation?

Hello I am a CSE student and this question was in my homework. ...
0
votes
1answer
21 views

Recurrence relations and induction: guessing the right bound

I'm currently dealing with the problem $$T(n)=T(\sqrt{n})+T(n-1)+n$$ This doesn't seem to show any pattern when continously broken down as a whole, but I was able to find the complexity of $$T(n)=T(n-...
1
vote
0answers
21 views

Space usage of recursive functions with no return

Consider an algorithm for reversing a sequence given below: ...
1
vote
1answer
23 views

What is the need for “some constant” times $n$?

I have a question regarding the following sentence: So we can make the following expressions: The best case running time of LINEARSEARCH is a constant function $T(n)=a$ OR $Θ(1)$ The worst case ...
1
vote
1answer
27 views

Equivalene of big O definitions (Limit Definition $\Longleftrightarrow$ Quantifier Definition)

I need to proof, that both definitions of the Big 0 notation are equiavlent, but I am not sure if my proof works both ways of the equivalence. Definitions: Let f,g be functions. $f(n)\in \mathcal{O}(...
0
votes
0answers
23 views

How to explain that a program that runs in NTIME(O(lg n)) is in the class P?

if a non-deterministic program executes only lg(n) decisions on each branch of the computation tree, then the problem this program solves is in P? That means, there is a deterministic algorithm that ...
2
votes
1answer
45 views

Big O and Little O

If $a_n = O(n^\alpha)$ and $b_n = o(n^\beta)$, prove that $a_nb_n = o(n^{(\alpha + \beta)})$ and $a_n+b_n = O(\max(n^\alpha, n^\beta))$. For the part about $a_nb_n = o(n^{(\alpha + \beta)})$, I get ...
1
vote
1answer
31 views

Finding n0, asymptotic analysis

I am attempting a textbook question about asymptotic analysis. The question goes: ** The number of operations executed by algorithms A and B is 8nlogn and 2n^2, respectively. Determine n0 such that A ...
8
votes
1answer
2k views

Are there any functions with Big O (Busy Beaver(n))?

So, I was reading this article by Scott Aaronson on big numbers, and he mentioned that the Busy Beaver sequence increases faster than all sequences computable by Turing Machines. Faster than ...
4
votes
2answers
111 views

Upper bounds for a binomial coefficient

I have an algorithm with worst-case time complexity in $\mathcal O (\binom{k}{p-1})$, where $k$ is a parameter and $p$ is the input size of that algorithm. I further have determined that $p-1 \leq k $...
0
votes
0answers
26 views

Time complexity of a recursive algorithm with two lists as parameters

The goal is to find the function T which describes the time complexity of an algorithm who merges two lists (but the lists are given inversely sorted). The problem is that recursive calls depend on an ...
1
vote
1answer
56 views

Simplify $O(\min(m, n))$?

I know that $O(\max(m, n)) = O(m + n)$, but is there a similar simplification for $O(\min(m, n))$? It could be $O(n) \cap O(m)$ but it does not simplify the notation that much…
0
votes
1answer
14 views

How do I work out the recurrence relation of the given function?

I am looking to find the recurrence relation (RR) of the fnA(), but I am unsure how $n$ is to be represented. (More specifically, I am trying to work out the ...
1
vote
1answer
26 views

$g ( n ) ∈ ω ( 1 )$ and $f ( n ) ∈ o ( g ( n ) )$ imply $2 f ( n ) ∈ o ( 2 g ( n ) )$

Prove that if $g ( n ) ∈ ω ( 1 )$ and $f ( n ) ∈ o ( g ( n ) )$, then $2 f ( n ) ∈ o ( 2 g ( n ) )$. I was going over this question in my Algorithms class and could'nt understand why first condition ...
0
votes
0answers
28 views

what is the complexity of the below code? [duplicate]

I wanted to calculate the complexity of this pseudocode. In my knowledge, it is $n^2$ because the last loop only runs 8 times. I wrote a program to test it tends to run 8^logn (approximately). can you ...
0
votes
0answers
35 views

The following time complexity is right for the given algorirthm

Calculate the complexity of the algorithm as follows O (n ^ 2) Would it be correct? ...
3
votes
1answer
565 views

Arrange in increasing order of asymptotic complexity

I have the following functions that I need to rank in increasing order of Big-O complexity: $$(\log n)^3, 10\sqrt n, n\log n, n\sqrt n, n^4 + n^3, (2.1)^n \cdot n^2, 3^n, 2^n \cdot n^3, n! + n, n^n. $$...
0
votes
1answer
24 views

Using Limits to Determine Asymptotic Relationship

Let's say we have $3^{4n}$ and $4^{3n}$. With the note of The Asymptotic Cheat Sheet from MIT. We should first calculate the lim n->infinity $3^{4n}$/$4^{3n}$. and it result is $\infty$. In the ...
1
vote
1answer
45 views

Difficult reccurence with two variables

My question is a follow-up for the following thread: Solving unusual recurrence with two variables I baisically have the same reccurence relation but with a small change--- $$T(n,k) = T(n-1,k)+T(n-m,k+...
0
votes
0answers
24 views

Asymptotic Notation sanity check for f(x) and g(x) [duplicate]

For each of the 2 pairs of functions I need to figure out the following: g(n) = Θ(h(n))? g(n) = O(h(n))? g(n) = Ω(h(n))? g(n) = o(h(n))? g(n) = ω(h(n))? Pair one g(n) = (64)(n/4), h(n) = 256(n/8) ...
0
votes
1answer
49 views

Comparing the big-$O$ of these four functions

Sometimes you can substitute values for $n_0$ and $c$ in the big-$O$ equation and compare two functions. Or take limits and compare two functions. But for the following functions, for example, taking ...
1
vote
1answer
41 views

Determing Big Oh Of Given Data

I'm trying to determine the big O time complexity of the following data set where the first column is the input size, and the second column is the execution time in seconds. Where possible, I should ...
0
votes
0answers
25 views

Time complexity for computing the highest degree vertex

Consider an undirected and unweighted graph with $n=|V|$ nodes and $m=|E|$ edges stored in adjacency matrix format. What is the time complexity of finding the highest-degree vertex, assuming the ...
0
votes
0answers
4 views

Complexity Analysis for complex nested loops [duplicate]

What is the general approach for time complexity analysis when you have a loop structure which is complex? For example if the length of the inner loop is some function o the iteration of the outer ...
2
votes
1answer
42 views

Is it true that $f(n) = c\cdot g(n) + O(g(n))$ implies $f(n) = O(g(n))$?

Is this true for all $n$ and some $c>0$? I'm thinking the answer is yes, but I'm not sure. My thinking is as follows: $f(n) = c\cdot g(n)$ for all $n$ and some $c>0$ is the definition of Big-Oh. ...
1
vote
1answer
29 views

What do these Big-O notations mean in context of comparison

What do the following mean, in the context of greater than, or smaller than? $$ O(n \log ⁡n) > O(n) $$ $$ O(nlogn) < O(n^2)...
1
vote
2answers
151 views

Time complexity of pairs in array double loop

I know, that the following is: O(n^2), ...
0
votes
1answer
42 views

How to calculate the runtime of a following code?

Could someone explain how to calculate the Big O notation for a runtime of a snippet of a code? ...
1
vote
1answer
35 views

Big-O of iterating through nested structure

While trying to understand complexity I run into an example of going through records organized in following way: ...
-1
votes
1answer
33 views

big theta prove

Prove that $3n^3 - 6n^2 + 9n - 9\log n \in \Theta(n^3)$ using So, how can I prove this by big theta definition? I don't what I should do with the log function
1
vote
2answers
98 views

Can $n = O(n^2)$?

I'm reading Data Structures and Algorithms by Goodrich. The explanation that he gives for Big Oh notation is given below: Let $f(n)$ and $g(n)$ be functions mapping positive integers to positive real ...
0
votes
1answer
41 views

How to calcualte the Big-O complexity of the following algorithm?

I have been trying to calculate the Big-O of the following algorithm and it is coming out to be O(n^5) for me. I don't know what the correct answer is but most of my colleagues are getting O(n^3). <...
2
votes
5answers
245 views

Big O notation for Average case in Linear search

Average case complexity for linear search is (n+1)/2 i.e, half the size of input n. The average case efficiency of an algorithm can be obtained by finding the average number of comparisons as given ...
3
votes
3answers
168 views

What is the complexity of $i^i$?

What is the complexity of the following algorithm in Big O: for(int i = 2; i < n; i = i^i) { ...do somthing } I'm not sure if there is a valid operator to ...
0
votes
0answers
28 views

Time complexity about Maximum subarray

I recently came across a function called the strawman algorithm which the pseudo code looks like this: ...
1
vote
2answers
91 views

Solving unusual recurrence with two variables

I have the following recurrence relation: $$T(n,k) = T(n-1,k)+T(n-1,k+1)$$ With the following base cases (for some given constant $C$): For all $x \leq C$ and for any $k$: $T(x,k)=1$ For all $y \geq C$...
2
votes
2answers
90 views

How does f(n) < cg(n) specify time?

I have been reading this tutorial on time complexity, and I am a bit puzzled on its explanation of big $O$ notation. It writes: $O(g(n)) = $ { $f(n)$ : there exist positive constants $c$ and $n_0$ ...
0
votes
1answer
37 views

Intro to Algorithms: asymptotic function analysis

I'm reading "Introduction to Algorithms" 3rd edition by Cormen, Leiserson, Rivest, Stein Page 46. The authors place formal upper and lower bounds on a function which is quadratic. Can ...
-1
votes
1answer
65 views

What is Simple Uniform Hashing, and why searching a hashtable has complexity Θ(n) in the worst case

Can anyone explain nicely what Simple Uniform Hashing is, and why searching a hashtable has complexity Θ(n) in the worst case if we don’t have uniform hashing (where n is the number of elements in the ...
-1
votes
1answer
39 views

How to know if time complexity is O(n+m) or O(n*m)

I'm having difficulty understanding when can we know if the time complexity of an algorithm is n+m or n*m Is the time complexity of the following algo O(n+m) or O(n*m) Can you please point me to a ...
0
votes
3answers
107 views

Sum rule for Big-O with equal complexity-functions?

One property of the Big-O-notation is the sum rule, which states that when I have two functions $f_1$ and $f_2$ and their corresponding complexity functions are $g_1$ and $g_2$, then the combined ...
1
vote
0answers
44 views

Complexity Values for Specific Code/Functions

(1) Assume a function $f:\mathbb{Z^+}\rightarrow\mathbb{R}$ that's defined in a way that utilizes, say, eight basic computations, including addition, subtraction, division, multiplication, (positive ...
1
vote
1answer
41 views

How to solve recursion with two separate converges rates

What is the correct way to solve the following recursion: $T(n)=T(\lceil\frac{n}{2}\rceil) + T(n-2)$ Or basically any recursion that has two parts which converge in a different rate. I'm trying to get ...
0
votes
1answer
66 views

How do you calculate the running time using Big-O notatation?

I'm still new to Data Structure and Algorithm and therefore I would like to ease my doubts. I'm required to find the Big-O running time of myMethod(): ...
1
vote
0answers
73 views

What is Big O of a loop with square root inside?

Knowing that O(n^2) > O(nlogn) > O(n) > O(sqrt(n)) > O(logn) > O(1) and having below python code: ...
0
votes
2answers
97 views

Time complexity of printing prime numbers within a range?

I've written an answer to this question, which asks about the following: What is the time complexity for the given code that prints prime numbers from start to <...
5
votes
1answer
59 views

Does big-Oh impose an ordered partition on the set of the “usual” functions?

The example in this answer proves the fact familiar to CS students - that the "big-O" is not a total order. However, most algorithm running times analyzed using big-Oh notation are not ...