What is the Big Theta runtime of this function, where n is the length of the list? def f(1st): i = 1 while i < len(1st): j = i + 1 while j / 2 > i: 1st[j] j = j + 1 i i+j %3D i + 1 %3D

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question

choose the correct answer.

What is the Big Theta runtime of this function, where n is the length of the list?
def f(1st):
i = 1
while i < len(1st):
j = i + 1
while j / 2 > i:
1st[j]
j = j + 1
i = i + 1
i+j
Transcribed Image Text:What is the Big Theta runtime of this function, where n is the length of the list? def f(1st): i = 1 while i < len(1st): j = i + 1 while j / 2 > i: 1st[j] j = j + 1 i = i + 1 i+j
Theta(log n)
Theta(n)
Theta(n log n)
Theta(n^2)
This code does not terminate.
This code does not have a tight Theta bound.
Transcribed Image Text:Theta(log n) Theta(n) Theta(n log n) Theta(n^2) This code does not terminate. This code does not have a tight Theta bound.
Expert Solution
steps

Step by step

Solved in 2 steps

Blurred answer
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education