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
2
votes
2answers
43 views

Is $\log(n-1) \in \Omega(\log(n))$?

I saw this question Can I simplify log(n+1) before showing that it is in O(log n)? and wanted to know if a similar situation was also true. Namely, is $\log(n-1) \in \Omega(\log(n))$?
1
vote
3answers
41 views

Is $n \log n$ in $O(n^{1.46-\varepsilon})$?

I am trying to figure out the solution of the recurrence relation $$T(n) = 5T(n/3) + n \log n$$ using the Master Method. I am guessing that $f(n) = O(n^{1.46 - \varepsilon})$, but I am confused in the ...
0
votes
0answers
14 views
0
votes
3answers
42 views

Finding a $g(n)$ so that $f(n) = O(g(n))$

I am having trouble on the following algorithms question: Given $f(n) = \sum^n_{y{=}1} (n^5\cdot y^{22})$, I am trying to find a $g(n)$ such that $f(n) = O(g(n))$. I know that this means I need to ...
1
vote
1answer
36 views

Problem from the Cormen appendix C 1.13

I am currently working on CLRS 1.13. The idea is to use Stirling's approximation to prove that $${2n \choose n} = \frac{2^{2n}}{\sqrt{\pi n}} \left( 1 + O \left( \frac{1}{n} \right) \right)$$ Now ...
1
vote
2answers
52 views

Operations with Asymptotic Notations

I am wondering is anyone has something like a cheatsheet with all the operations between $O(n)$, $\Theta(n)$, $\Omega(n)$, $o(n)$, $\omega(n)$. For example, this is something I don't know how to solve:...
1
vote
1answer
55 views

why quicksort can have a best big o notation of (n log n)

I don't really quite understand why quicksort has a big $O$ notation of $(n \log n)$. I would like some help understanding what exactly $(n \log n)$ is, and then how it applies to quicksort. Also in $(...
1
vote
1answer
41 views

Asymptotic notation between two sets of variables

I have problems interpreting the definition of asymptotic notation where the functions involve two different set of variables. I am quite confident with the definition of $f(n) = O(g(n))$ and its ...
1
vote
1answer
76 views

Analyzing the Runtime of Shuffling Algorithm

The following is psuedocode used to shuffle the contents of an array $A$ of length $n$. As a subroutine for shuffle, there is a call to Random$(m)$ which takes $O(m^2)$ time for an input $m$. ...
-3
votes
2answers
84 views

Is there a real life example of algorithm that has running time $\Theta(1)$

I am a CS first year student, and as I was reviewing over the theta notation unit, I saw that $\Theta(1)$ exists. I was wondering if there was any real life example algorithm that has a running time ...
2
votes
2answers
64 views

Big Oh rules - How to argue in case of negative base

Let us say you have a function $C_n = (-2)^n + 2^n$. It would seem that it would be correct to assume that the running time of this algorithm would be $O(2^n)$. However, how would I go about arguing ...
8
votes
2answers
1k views

Isn't linear time O(n)?

In the question in this video about quicksort luckily picking the median in each recursive call. Tim Roughgarden, the presenter, says at 11:22 Partition needs really linear time, not just $O(n)$ time....
0
votes
0answers
14 views

When can theta be used for different values? [duplicate]

On the course material I am following we have been given an explanation for theta as being when omega and Oh 'sandwich' the run time, so it is bounded between the two values, at least I think this is ...
2
votes
2answers
77 views

What do you get when you add $O(n)$ to itself $n$ times?

I was watching this video on Algorithms and counting number of inversions and he mentioned being cautions when $O(n) + O (n) = O(n)$, saying that is not true if you add $O(n)$ to itself $n$ times. Is ...
0
votes
1answer
57 views

How to calculate O-Notation?

I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; What I would like to ask, if there is a certain way to find out O-Notation? Actually ...
1
vote
1answer
33 views

What's wrong with this substitution for master's method

I was hoping to solve the following recurrence by performing a simple substitution followed by the master's method: $$T\left(n\right)=T\left(n-1\right)+n^2$$ I did $$S\left(2^n\right)=S\left(2^{n-1}\...
0
votes
1answer
33 views

Help with model answer for time complexity

Hi I cannot understand why the best case for line 3 is n-1 and why it isnt just always n? I tried to write this in python to ...
0
votes
1answer
33 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
45 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
41 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
44 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
28 views

Space usage of recursive functions with no return

Consider an algorithm for reversing a sequence given below: ...
1
vote
1answer
27 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
29 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
49 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
52 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
3k 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 ...
5
votes
2answers
137 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
28 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
74 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
15 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
736 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
28 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
47 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
51 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
73 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
44 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
31 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
164 views

Time complexity of pairs in array double loop

I know, that the following is: O(n^2), ...
0
votes
1answer
51 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
36 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
35 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
100 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 ...